Question

求二叉树的最大深度

Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

二叉树的定义

 // Definition for a binary tree node.
 public class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
 }

Solutions

public class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        
        return Math.max(left, right) + 1;
    }
}

一开始忘记max函数怎么用，就写成了这样

if (left > right) {
            return left + 1;
        } else {
            return right + 1;
        }

One Line Show

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

Points

• 二叉树的数组表现
  [1,null,2,3]这样的数组，顺序为从上往下每行中的从左到右的节点。
  null表示空节点。[]表示空树。
  array[i]的左子树为array[i*2]，右子树为array[i*2+1]。

  BinaryTree.png

• 节点为null的处理

  if (root == null) {
      return 0;
  }

• 递归的效率
  当一个函数用它自己来定义时，就称为递归（recursive）的；

  纱布如我一开始是这样写的

if (maxDepth(root.left) >= maxDepth(root.right)) {
     return maxDepth(root.left) + 1;
 } else {
     return maxDepth(root.right) + 1;
}

多么直观，然后就感人的Time Limit Exceeded了。
这里大概是因为每次调用一次maxDepth都进行了一次递归，所以应该把maxDepth的结果保存成值再进行比较和返回。
这样写就没问题了

int left = maxDepth(root.left);
int right = maxDepth(root.right);
      
if (left > right) {
      return left + 1;
} else {
      return right + 1;
}

然后再精简点

return Math.max(maxDepth(root.right), maxDepth(root.left)) + 1;

TO DO

• 二叉树相关概念
• Math.max 源码分析