ツリー階層遍歴テンプレート

ツリー階層のテンプレートを巡回するには、次の手順に従います.

public void bfs(TreeNode root){
	Queue<TreeNode> queue=new LinkedList<>();//    
	queue.add(root);
	while(!queue.isEmpty()){
	    int cnt=queue.size();
	    //          ，           
	    while(cnt-->0){
	        TreeNode node=queue.poll();//      
	        list.add(node.val);//      
	        if(node.left!=null){
	            queue.add(node.left);
	        }
	        if(node.right!=null){
	            queue.add(node.right);
	        }
	    }
	    //       ，          ，          
	}
}

LeetCodeの3つの典型的な二叉木の層順は関連する問題型を遍歴している.
1.ツリーの層順遍歴(LeetCode 102)
ツリーを2つあげます.レイヤ順にループしたノード値を返してください.(つまり、左から右へすべてのノードに階層的にアクセスします).

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret=new ArrayList<>();
        if(root==null){
            return ret;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            int cnt=queue.size();
            ArrayList<Integer> list=new ArrayList<>();
            while(cnt-->0){
                TreeNode node=queue.poll();
                list.add(node.val);
                if(node.left!=null){
                    queue.add(node.left);
                }
                if(node.right!=null){
                    queue.add(node.right);
                }
            }
            ret.add(new ArrayList(list));
        }
        return ret;
    }
}

2.ツリーのジグザグ階層遍歴(LeetCode 103)
ツリーを2つ指定し、ノード値を返すのこぎり階層を巡ります.(すなわち、左から右へ、右から左へと次の層を遍歴し、このようにして層と層の間を交互に行う).

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ret=new ArrayList<>();
        boolean flag=false;
        if(root==null){
            return ret;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            int cnt=queue.size();
            ArrayList<Integer> list=new ArrayList<>();
            while(cnt-->0){
                TreeNode node=queue.poll();
                list.add(node.val);
                if(node.left!=null){
                    queue.add(node.left);
                }
                if(node.right!=null){
                    queue.add(node.right);
                }
            }
            flag=!flag;
            if(!flag){
                Collections.reverse(list);     
            }  
            ret.add(new ArrayList(list));  
        }
        return ret;
    }
}

3.ツリーの最大深さ(LeetCode 104)
ツリーに最大深さを指定します.ツリーの深さは、ルートノードから最も遠いリーフノードまでの最長パス上のノード数です.

class Solution {
    public int maxDepth(TreeNode root) {
    	int ret=0;
        if(root==null){
            return ret;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            int cnt=queue.size();
            ArrayList<Integer> list=new ArrayList<>();
            while(cnt-->0){
                TreeNode node=queue.poll();
                list.add(node.val);
                if(node.left!=null){
                    queue.add(node.left);
                }
                if(node.right!=null){
                    queue.add(node.right);
                }
            }
            ret++;
        }
        return ret;
    }
 }