二叉树的两道超高频考题

 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
26
27
28

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
    // 跳出递归
	if root == nil {
        return nil
    }

    // 祖先可能是 p,q
    if root == p || root == q {
        return root
    }

    // 祖先不是 p,q ，在左右子树上再次寻找
    left := lowestCommonAncestor(root.Left, p, q)
    right := lowestCommonAncestor(root.Right, p, q)

    // 左边没找到，返回右边
    if left == nil {
        return right
    }
    
    // 右边没找到，返回左边
    if right == nil {
        return left
    }

    // 左右都不为空，说明祖先在以 root 为根的子树中，返回 root
    return root
}

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

func maxPathSum(root *TreeNode) int {
    var dfs func(*TreeNode) int
    ans := math.MinInt

    dfs = func(node *TreeNode) int {
        if node == nil {
            return 0
        }

        leftMax := dfs(node.Left)
        rightMax := dfs(node.Right)
        curSum := leftMax + rightMax + node.Val
        ans = max(ans, curSum)
        return max(max(leftMax, rightMax)+node.Val, 0) // 0 代表不选
    }

    dfs(root)
    return ans
}