层次遍历的两种方式：递归与迭代

骑猪看日落 2022-08-04 09:19 217阅读 0赞

**树结构：**

public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
    
        }
    
    }

**二叉树的层次遍历方式一：递归调用**（参考网上的方法），先序遍历递归时多传递一个层次数，按照该层次数保存节点相关值。

private List<List<Integer>> resList = new ArrayList<List<Integer>>();
    public static void levelTraversal(int dep, TreeNode root) {
    <span>	</span>if(root == null) {
    	<span>	</span>return ;
    	}
    	if(resList.size() > dep) {
    		resList.get(dep).add(root.val) ;
    	} else {
    		List<Integer> r = new ArrayList<Integer>() ;
    		r.add(root.val) ;
    		resList.add(r) ;
    	}
    	
    	levelTraversal(dep+1, root.left);
    	levelTraversal(dep+1, root.right) ;
    }

**二叉树的层次遍历方式二：迭代**。使用队列实现

private List<List<Integer>> res = new ArrayList<List<Integer>>() ;
        public void levelTraversal(TreeNode root) {
            Queue<TreeNode> queue = new ArrayDeque<TreeNode>() ;
            Queue<TreeNode> qTmp = new ArrayDeque<TreeNode>() ;
             
            queue.add(root) ;
            while(!queue.isEmpty()) {
                while(!queue.isEmpty()) {
                    TreeNode tmp = queue.poll() ;
                    if(tmp.left != null) {
                        qTmp.add(tmp.left) ;
                    }
                    if(tmp.right != null) {
                        qTmp.add(tmp.right) ;
                    }
                }
                 
                List<Integer> list = new ArrayList<Integer>() ;
                while(!qTmp.isEmpty()) {
                    TreeNode t = qTmp.poll() ;
                    queue.add(t) ;
                    list.add(t.val) ;
                }
                if(list.size() > 0) {
                    res.add(list) ;
                }
    
            }
        }