104. 二叉树的最大深度

1、概要

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

可以使用前序求深度，也可以使用后序求高度。

• 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）
• 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从0开始还是从1开始）

根节点的高度就是二叉树的最大深度

2、思路

递归法

• 递归函数的参数和返回值

树的根节点，返回深度int类型

public int traverse(TreeNode root)

• 终止条件

空节点返回0

	if(root == null){
            return;
        }

• 单层递归

先求左子树深度，再求右子树深度，最后取左右最大值+1（算上当前中间节点）就是目前节点为根节点的树的深度。

int leftNum = traverse(root.left);
        int rightNum = traverse(root.right);

        return Math.max(leftNum,rightNum)+1;

迭代法

层序遍历模版，每层深度+1

3、代码

class Solution {
  

    public int maxDepth(TreeNode root){
        //return traverse(root);

        return order(root);
    }

    public int order(TreeNode node){
        if(node == null){
            return 0;
        }
        Queue<TreeNode> que = new LinkedList<TreeNode>();
        que.offer(node);
        //深度计数器
        int len = 0;

        while(!que.isEmpty()){
            
            int deep = que.size();

            while(deep> 0){
                TreeNode cur = que.poll();
                
                if(cur.left!=null){
                    que.offer(cur.left);
                }
                if(cur.right!=null){
                    que.offer(cur.right);
                }
                deep--;
            }
            //深度累加
            len++;
        }
        return len;
    }
    
     public int traverse(TreeNode root){//后序
        if(root == null){
            return 0;
        }

        int leftNum = traverse(root.left);
        int rightNum = traverse(root.right);

        return Math.max(leftNum,rightNum)+1;
    }


}

4、相关题目

559. N 叉树的最大深度

class Node {

public int val;

public List children; //集合，可以用get获取

public Node() {}

public Node(int _val) {

​ val = _val;

}

public Node(int _val, List _children) {

​ val = _val;

​ children = _children;

}

N叉树定义，值与孩子

class Solution {
    
    public int maxDepth(Node root) {
        
        //return reCurSion(root);
        return iTeRation(root);

    }

    private int reCurSion(Node root){
        if(root == null){return 0;}

        int depth = 0;

        if(root.children !=null){
            for(Node child : root.children){
                depth = Math.max(depth,maxDepth(child));
            }
        }
        return depth +1;
    }
    private int iTeRation(Node root){
        if(root == null){return 0;}
        int depth = 0;
        Queue<Node> que = new LinkedList<>();
        que.offer(root);
        while(!que.isEmpty()){
            depth++;
            int len = que.size();
            while(len > 0){
                Node cur = que.poll();
                for(int i=0;i<cur.children.size();i++){
                    if(cur.children.get(i) != null){
                        que.offer(cur.children.get(i));
                    }
                }
                len--;
            }
        }
        return depth;
    }
    
}