二叉树：树的最大深度

104. 二叉树的最大深度

给定一个二叉树，找出其最大深度。

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

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

给定二叉树 [3,9,20,null,null,15,7]，

    3
   /   9  20
    /     15   7

返回它的最大深度 3 。

思路

递归法

1. 确定递归函数的参数和返回值：参数就是传入树的根节点，返回就返回这棵树的深度，所以返回值为int类型。

2. 确定终止条件：如果为空节点的话，就返回0，表示高度为0。

3. 确定单层递归的逻辑：先求它的左子树的深度，再求的右子树的深度，最后取左右深度最大的数值 再+1 （加1是因为算上当前中间节点）就是目前节点为根节点的树的深度。

层序遍历

最大的深度就是二叉树的层数，和层序遍历的方式极其吻合。

所以这道题的迭代法就是一道模板题，可以使用二叉树层序遍历的模板来解决的。

代码

递归法

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
     }
}

层序遍历

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) return 0;
        int depth = 0;
        Queue<TreeNode> que = new LinkedList<TreeNode>();
        que.add(root);
        while(!que.isEmpty()){
            int size = que.size();
            depth++;
            for(int i=0;i<size;i++){
                TreeNode node = new TreeNode();
                node = que.poll();
                if(node.left != null){
                    que.add(node.left);
                }
                if(node.right != null){
                    que.add(node.right);
                }
            }
        }
        return depth;
    }
}

二叉树：树的最大深度

原文：https://www.cnblogs.com/luedong/p/14699831.html