129. 求根节点到叶节点数字之和

• 思路
  • example
  • 递归：前序遍历
    • 注意判断 叶子节点
    • 隐含回溯
• 复杂度. 时间：O(?), 空间: O(?)

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        def traversal(root, pathSum):
            nonlocal totalSum 
            if root == None:
                return  
            pathSum = pathSum * 10 + root.val 
            if root.left == None and root.right == None: # root是叶子节点
                totalSum += pathSum  
                return   
            traversal(root.left, pathSum)
            traversal(root.right, pathSum) 
            return  
        totalSum = 0
        traversal(root, 0)
        return totalSum  

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        def traverse(root, pathSum):
            nonlocal total 
            if root == None:
                return 
            pathSum = pathSum*10 + root.val 
            if root.left == None and root.right == None:
                total += pathSum 
                return 
            traverse(root.left, pathSum) 
            traverse(root.right, pathSum) 
        total = 0 
        traverse(root, 0)
        return total 

• 另一个版本

class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        res = 0
        path = []
        def backtrace(root):
            nonlocal res
            if not root: return # 节点空则返回
            path.append(root.val)
            if not root.left and not root.right: # 遇到了叶子节点
                res += get_sum(path)
            if root.left: # 左子树不空
                backtrace(root.left)
            if root.right: # 右子树不空
                backtrace(root.right)
            path.pop()

        def get_sum(arr):
            s = 0
            for i in range(len(arr)):
                s = s * 10 + arr[i]
            return s

        backtrace(root)
        return res

• 后序?

1382. 将二叉搜索树变平衡

• 思路
  • example
  • 转化为数组（中序）
  • 取中间位置，递归构造左右子树
• 复杂度. 时间：, 空间:

class Solution:
    def balanceBST(self, root: TreeNode) -> TreeNode:
        # 1. 转化为有序数组
        def traversal(root):
            if root == None:
                return 
            traversal(root.left)
            path.append(root.val)
            traversal(root.right)
            return  
        path = []
        traversal(root)  
        # 2. 基于有序数组构造平衡二叉树
        def construct(nums, left, right):
            if left > right:
                return None  
            mid = left + (right - left) // 2
            root = TreeNode(nums[mid])
            root.left = construct(nums, left, mid-1)
            root.right = construct(nums, mid+1, right)
            return root  
        res = construct(path, 0, len(path)-1)
        return res  

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def balanceBST(self, root: TreeNode) -> TreeNode:
        def traverse(root):
            if root == None:
                return 
            traverse(root.left) 
            path.append(root.val) 
            traverse(root.right) 
        def constructBST(nums, left, right): 
            if left > right:
                return None 
            mid = left + (right - left) // 2
            root = TreeNode(nums[mid])
            root.left = constructBST(nums, left, mid-1)
            root.right = constructBST(nums, mid+1, right)
            return root 
        path = [] 
        traverse(root) 
        if len(path) == 0:
            return None 
        return constructBST(path, 0, len(path)-1)   

100. 相同的树

• 思路
  • example
  • 递归：前序，后序
• 复杂度. 时间：O(?), 空间: O(?)

class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if p == None and q == None:
            return True  
        if p == None or q == None:
            return False  
        if p.val != q.val:
            return False  
        return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)  

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if p == None and q == None:
            return True 
        if p == None or q == None:
            return False 
        if p.val != q.val:
            return False 
        valid_left = self.isSameTree(p.left, q.left) 
        if valid_left == False:
            return False 
        valid_right = self.isSameTree(p.right, q.right) 
        if valid_right == False:
            return False 
        return True 

116. 填充每个节点的下一个右侧节点指针

• 思路
  • example
  • 层序遍历，deque
• 复杂度. 时间：O(n), 空间: O(n)

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""
class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        que = collections.deque() 
        if root:
            que.append(root) 
        while que:
            size = len(que)  
            for i in range(size):
                node = que.popleft() 
                if i == 0:
                    pre = node 
                else:
                    pre.next = node 
                    pre = node 
                if node.left:
                    que.append(node.left) 
                if node.right:
                    que.append(node.right) 
        return root 

• 进阶：你只能使用常量级额外空间。
  • 链表式操作

一层层用next连接起来，这样可以实现层序遍历
再把下一层的节点顺序连接起来即可

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        cur = root  
        while cur:
            dummyhead = Node(0)
            pre = dummyhead  
            while cur: # 同层遍历
                if cur.left: # 左节点
                    pre.next = cur.left  
                    pre = cur.left 
                if cur.right: # 右节点 
                    pre.next = cur.right  
                    pre = cur.right 
                cur = cur.next  # 同层下一节点
            cur = dummyhead.next # 下一层第一个节点
        return root 

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""
class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        cur = root 
        while cur: # 对每层第一个node循环
            dummyhead = Node(-1)
            pre = dummyhead 
            while cur: # 层内循环
                if cur.left:
                    pre.next = cur.left 
                    pre = cur.left 
                if cur.right:
                    pre.next = cur.right 
                    pre = cur.right  
                cur = cur.next 
            cur = dummyhead.next # 下一层的第一个node
        return root