二叉树 0

二叉树系列 0

  • 前中后序是遍历二叉树过程中处理每一个节点的三个特殊时间点

  • 对节点的访问顺序其实是一样的，但是输出顺序不一样

  • 如果能遍历一遍得到结果的，就可以用遍历法。而如果涉及子树结果的（可分解为子问题），就可以用递归的方法。

  • 后序位置才能通过返回值获取子树的信息。一旦发现题目和子树有关，那大概率要给函数设置合理的定义和返回值，在后序位置写代码了。

二叉树的最大深度

https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
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 
    }
    return b
}

遍历

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
// 记录最大深度
int res = 0;
// 记录遍历到的节点的深度
int depth = 0;

// 主函数
int maxDepth(TreeNode root) {
	traverse(root);
	return res;
}

// 二叉树遍历框架
void traverse(TreeNode root) {
	if (root == null) {
		// 到达叶子节点，更新最大深度
		res = Math.max(res, depth);
		return;
	}
	// 前序位置
	depth++;
	traverse(root.left);
	traverse(root.right);
	// 后序位置
	depth--;
}

二叉树的直径

https://leetcode-cn.com/problems/diameter-of-binary-tree/

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

func diameterOfBinaryTree(root *TreeNode) int {
    maxDiameter = 0
    maxDepth(root)
    return maxDiameter
}

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    maxLeft, maxRight := maxDepth(root.Left), maxDepth(root.Right)
    myDiameter := maxLeft + maxRight
    maxDiameter = max(maxDiameter, myDiameter)
    return 1 + max(maxLeft, maxRight)
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}