日拱两卒（六）

50#

二叉树中的最大路径和。

维护每个节点的左右两条链。

因为有负数，注意和零比较。

1
class Solution:
2
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
3
        if root == None:
4
            return 0
5

6
        N = 3 * 10000 + 10
7
        ans = -N * 1000
8

9
        s = dict()
10

11
        def dfs(u):
12
            nonlocal ans
13
            if u.left is None:
14
                s[(u, 0)] = 0
15
            if u.right is None:
16
                s[(u, 1)] = 0
17
            if u.left:
18
                dfs(u.left)
19
                s[(u, 0)] = max(0, max(s[(u.left, 0)], s[(u.left, 1)]) + u.left.val)
20
            if u.right:
21
                dfs(u.right)
22
                s[(u, 1)] = max(0, max(s[(u.right, 0)], s[(u.right, 1)]) + u.right.val)
23
            ans = max(ans, u.val + s[(u, 0)] + s[(u, 1)])
24

25
        dfs(root)
26

27
        return ans

49#

二叉树的最近公共祖先。

简单递归。

1
class Solution:
2
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
3
        if root is None or root == p or root == q:
4
            return root
5

6
        l = self.lowestCommonAncestor(root.left, p, q)
7
        r = self.lowestCommonAncestor(root.right, p, q)
8

9
        if l and r:
10
            return root
11
        if l:
12
            return self.lowestCommonAncestor(l, p, q)
13
        if r:
14
            return self.lowestCommonAncestor(r, p, q)
15
        return None

48#

路径总和III。

求路径和等于Target的路径数。这里的路径只向下。

1
class Solution:
2
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
3
        def getSum(root, target) -> int:
4
            if root is None:
5
                return 0
6
            res = 0
7
            if root.val == target:
8
                res += 1
9
            res += getSum(root.left, target - root.val)
10
            res += getSum(root.right, target - root.val)
11
            return res
12

13
        if root is None:
14
            return 0
15
        return getSum(root, targetSum) + self.pathSum(root.left, targetSum) + self.pathSum(root.right, targetSum)

47#

从前序与中序遍历序列构造二叉树。

这个初见不会，甚至完全不知道怎么做。

通过看前序的第一个元素能找到根，在中序里找到这个元素，那么就知道了左子树和右子树的大小。

然后就去递归解子问题。

好巧妙，我的脑子好僵化。

1
class Solution:
2
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
3
        if not preorder:
4
            return None
5
        left_cnt = inorder.index(preorder[0])
6
        left = self.buildTree(preorder[1: 1 + left_cnt], inorder[:left_cnt])
7
        right = self.buildTree(preorder[1 + left_cnt:], inorder[1 + left_cnt:])
8
        return TreeNode(preorder[0], left, right)

46#

二叉树展开为链表。

右左根遍历从后往前构造。不要忘记把左指针置空。

1
class Solution:
2
    def flatten(self, root: Optional[TreeNode]) -> None:
3
        if root is None:
4
            return
5

6
        end = None
7

8
        def dfs(cur):
9
            nonlocal end
10
            if cur.right:
11
                dfs(cur.right)
12
            if cur.left:
13
                dfs(cur.left)
14
            cur.right = end
15
            cur.left = None
16
            end = cur
17

18
        dfs(root)

45#

二叉树的右视图。

按深度遍历，每一层的最右边是答案。

1
class Solution:
2
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
3
        ans = []
4

5
        def dfs(root, depth):
6
            if root is None:
7
                return
8

9
            if len(ans) > depth:
10
                ans[depth] = root.val
11
            else:
12
                ans.append(root.val)
13

14
            dfs(root.left, depth + 1)
15
            dfs(root.right, depth + 1)
16

17

18
        dfs(root, 0)
19
        return ans

44#

二叉搜索树中第K小的元素。

按子树大小来筛。

题解更简单，二叉搜索树的中序遍历是一个递增序列，其实就是求中序遍历的第K个元素。

1
class Solution:
2
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
3
        @cache
4
        def sz(cur) -> int:
5
            if cur is None:
6
                return 0
7
            sz_left = sz(cur.left)
8
            sz_right = sz(cur.right)
9
            return 1 + sz_left + sz_right
10

11
        sz(root)
12

13
        def dfs(cur, k) -> int:
14
            sz_left = sz(cur.left)
15
            if k == sz_left + 1:
16
                return cur.val
17
            elif k <= sz_left:
18
                return dfs(cur.left, k)
19
            elif k > sz_left + 1:
20
                return dfs(cur.right, k - sz_left - 1)
21

22
        return dfs(root, k)

43#

验证二叉搜索树。

昨晚上面那道题就知道这里可以检查中序遍历。

1
class Solution:
2
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
3
        check = []
4

5
        def dfs(cur):
6
            if cur is None:
7
                return
8
            dfs(cur.left)
9
            check.append(cur.val)
10
            dfs(cur.right)
11

12
        dfs(root)
13

14
        for i in range(len(check) - 1):
15
            if check[i] >= check[i + 1]:
16
                return False
17
        return True

42#

将有序数组转为二叉平衡搜索树。

挑出中间的数，简单递归。

1
class Solution:
2
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
3
        if len(nums) == 0:
4
            return None
5
        return TreeNode(val=nums[len(nums) // 2], left=self.sortedArrayToBST(nums[:len(nums) // 2]), right=self.sortedArrayToBST(nums[len(nums) // 2 + 1:]))

41#

二叉树的层序遍历。

按层级输出。

1
class Solution:
2
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
3
        ans = []
4
        def dfs(cur, dep):
5
            if cur is None:
6
                return
7
            if dep >= len(ans):
8
                ans.append([cur.val])
9
            else:
10
                ans[dep].append(cur.val)
11
            dfs(cur.left, dep + 1)
12
            dfs(cur.right, dep + 1)
13

14
        dfs(root, 0)
15
        return ans