二叉树的层次遍历变形

╰半夏微凉° 2022-05-18 11:17 222阅读 0赞

![70][]

import java.util.*;
    class TreeNode {
          int val;
          TreeNode left;
          TreeNode right;
          TreeNode(int x) { val = x; }
      }
    
    public class Solution {
    
    
         //二叉树的层次遍历
        public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
    
            return levelOrderHelper(root);
    
        }
    
        //二叉树的层次遍历（非递归）
        public ArrayList<ArrayList<Integer>> levelOrderHelper(TreeNode root){
            ArrayList<ArrayList<Integer>>arr=new ArrayList<>();
             if(root==null)
               return arr;
             Queue<TreeNode>queue=new LinkedList<>();  //运用队列
             queue.offer(root);
             while(!queue.isEmpty()){
                 ArrayList<Integer>level=new ArrayList<>();
                 int levelNum=queue.size();
                 while(levelNum--!=0){
                    TreeNode temp=queue.poll();
                    level.add(temp.val);
                    if(temp.left!=null) queue.offer(temp.left);
                    if(temp.right!=null) queue.offer(temp.right);
                 }
                 arr.add(level);
             }      
             return arr;
        }
    
        //二叉树的层次遍历(递归实现)
        public void  levelOrderHelper01(TreeNode root){
             if(root==null)
               return ;
             Queue<TreeNode>queue=new LinkedList<>();
             queue.offer(root);
             while(!queue.isEmpty()){
                  TreeNode temp=queue.poll();
                  System.out.println(temp.val);
                  if(temp.left!=null)
                     levelOrderHelper01(temp.left);
                  if(temp.right!=null)
                     levelOrderHelper01(temp.right);
             }
        }
    
        public static void main(String[]args){
           //System.out.println("Hello World!");
           TreeNode root=new TreeNode(3);
           root.left=new TreeNode(9);
           root.right=new TreeNode(20);
           root.right.left=new TreeNode(15);
           root.right.right=new TreeNode(7);
           Solution s=new Solution();
           System.out.println(s.levelOrder(root));
    
    
        }
    }

![这里写图片描述][70 1]

[70]: /images/20220518/6548d10752b942b08cd341f545fdb551.png
[70 1]: /images/20220518/44fc10f903ce4f0c8d91c3b68009f2d9.png