Leetcode104.求二叉树的最大深度

题目描述

递归法

class Solution {
        public int maxDepth(TreeNode root) {
            if (root == null) { //帮助下面的else语句判空
                return 0;
            } else {
                int leftHeight = maxDepth(root.left);
                int rightHeight = maxDepth(root.right);
                /**
                 * 要注意的点
                 * 1. 这个return是写在else语句里面的，如果放外面，就访问不到leftHeight了。
                 * 2. Math.max(leftHeight, rightHeight) 是这行代码的关键
                 */
                return Math.max(leftHeight, rightHeight) + 1;
            }
        }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

用f代表maxDepth()函数，执行过程解析

f(3)
⇒ max(f(9),f(20))+1
⇒ max( 
			 (max(f(null),f(null)+1),   (max(f(15),f(7))+1) 
			) +1
⇒ max( 
				(max(0,0)+1), 
			（max(f(15),f(7))+1) 
			)  + 1
⇒ max(
				1, 
				(max(       (max(f(null), f(null)+1)， （max(f(null), f(null))+1)      ) +1)
			) +1
⇒ max(
				1,
				(max( (max(0,0)+1),  (max(0,0)+1))+1)
			) +1
⇒ max(
				1,
				(max(1,1)+1)
			）+1
⇒ max(1,2)+1
⇒ 3


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25