104.二叉树的最大深度.md

104. 二叉树的最大深度

url

题目

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

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

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

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

方法

可递归，可遍历

• 注意结束条件，如果为null则返回0
• 递归不断比较左右谁的深度大

code

js

let maxDepth = root => {
    return root === null ? 0 : 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

go

func maxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	return 1 + Max(maxDepth(root.Left), maxDepth(root.Right))
}
func Max(a, b int) int {
	if a > b {
		return a
	} else {
		return b
	}
}

java

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        int depth = 0;
        Queue<Pair<TreeNode, Integer>> queue = new LinkedList<>();
        queue.add(new Pair(root, 1));
        while (!queue.isEmpty()){
            Pair<TreeNode, Integer> cur = queue.poll();
            root = cur.getKey();
            int curDepth = cur.getValue();
            if (root != null) {
                depth = Math.max(depth, curDepth);
                queue.add(new Pair(root.left, curDepth + 1));
                queue.add(new Pair(root.right, curDepth + 1));
            }
        }
        return depth;
    }
}