LeetCode算法题整理（二叉树篇）Tree

树的定义

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None    def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
        ans = 0
        if root:
            if low <= root.val <= high:
                ans += root.val
                ans += self.rangeSumBST(root.left, low, high)
                ans += self.rangeSumBST(root.right, low, high)
            elif root.val < low:
                ans += self.rangeSumBST(root.right, low, high)
            else:
                ans += self.rangeSumBST(root.left, low, high)
        return ans
        self.right = None

144. Binary Tree Preorder Traversal

二叉树前序遍历

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,2,3]

方法一：iteratively

def preorderTraversal(self, root: 'TreeNode') -> 'List[int]':
    ans, stack = [], root and [root]
    while stack:
        node = stack.pop()
        if node:
            ans.append(node.val)
            stack.append(node.right)
            stack.append(node.left)
    return ans

方法二：recursively

def preorder_traversal(root):
    if not root:
        return []
    return [root.val] + self.preorderTraversal(root.left) + \
        self.preorderTraversal(root.right)

589. N-ary Tree Preorder Traversal

N-叉树的前序遍历。N叉树和二叉树有个区别，就是N叉树不需要考虑子节点知否为空，做单独的判断。原题

方法一：recursively.

def preorder(self, root):
    if not root:
        return []
    res = [root.val]
    for child in root.children:
        res += self.preorder(child)
    return res

方法二：iteratively.

def preorder(self, root):
    res, stack = [], root and [root]
    while stack:
        node = stack.pop()
        res.append(node.val)
        stack.extend(reversed(node.children))
    return res

94. Binary Tree Inorder Traversal

中序遍历二叉树

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,3,2]

方法一：使用栈迭代。

def inorderTraversal(self, root: TreeNode) -> List[int]:
    stack, ans = [], []
    while stack or root:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        ans.append(root.val)
        root = root.right
    return ans

方法二：Morris Traversal.

def inorderTraversal(self, root: TreeNode) -> List[int]:
    cur, ans = root, []
    while cur:
        if not cur.left:
            ans.append(cur.val)
            cur = cur.right
        else:
            pre = cur.left
            # 找到当前节点左子树中最右的右节点
            while pre.right and pre.right != cur:
                pre = pre.right
                
            if not pre.right:
                # 找到最右的节点，连接到根节点
                pre.right = cur
                cur = cur.left
            # 恢复节点
            else:
                pre.right = None
                ans.append(cur.val)
                cur = cur.right
                
    return ans

145. Binary Tree Postorder Traversal

后序遍历二叉树

Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [3,2,1]

方法一：根右左，再倒序。

def postorder_traversal(root):
    res, stack = [], [root]
    while stack:
        node = stack.pop()
        if node:
            res.append(node.val)
            stack.append(node.left)
            stack.append(node.right)
    return res[::-1]

方法二：思想: 使用last作为判断是否该节点的右子树完成遍历，如果一个node.right已经刚刚遍历完毕，那么将last==node.right，否则将会寻找node.right。

def postorderTraversal(self, root):
    res, stack, node, last = [], [], root, None
    while stack or node:
        if node:
            stack.append(node)
            node = node.left
        else:
            node = stack[-1]
            if not node.right or last == node.right:
                node = stack.pop()
                res.append(node.val)
                last, node = node, None
            else:
                node = node.right    
    return res

方法三：使用boolean判断一个节点是否被遍历过

def postorderTraversal(self, root):
    res, stack = [], [(root, False)]
    while stack:
        node, visited = stack.pop()
        if node:
            if visited:
                res.append(node.val)
            else:
                stack.append((node, True))
                stack.append((node.right, False))
                stack.append((node.left, False))                
    return res

方法四：dfs.

def postorderTraversal(self, root: 'TreeNode') -> 'List[int]':
    ans = []

    def dfs(node):
        if not node:
            return 
        dfs(node.left)
        dfs(node.right)
        ans.append(node.val)
        
    dfs(root)
    return ans

590. N-ary Tree Postorder Traversal

N-叉树的后序遍历。原题

方法一：recursively.

def postorder(self, root):
    if not root:
        return []
    return sum([self.postorder(child) for child in root.children], []) + [root.val]

方法二：iteratively and reversed.

def postorder(self, root):
    res, stack = [], root and [root]
    while stack:
        node = stack.pop()
        res.append(node.val)
        stack.extend(node.children)
    return res[::-1]

方法三：iteratively and flag.

def postorder(self, root):
    res, stack = [], root and [(root, False)]
    while stack:
        node, visited = stack.pop()
        if visited:
            res.append(node.val)
        else:
            stack.append((node, True))
            stack.extend((n, False) for n in reversed(node.children))
    return res

100. Same Tree

判断相同的二叉树。原题

Input:     1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

Output: true

方法一：recursively

def isSameTree(self, p: 'TreeNode', q: 'TreeNode') -> 'bool':
    if p and q:
        return (p.val==q.val and self.isSameTree(p.left, q.left) and 
                self.isSameTree(p.right, q.right))
    else:
        return p is q

方法二：recursively, tuple

def is_same_tree(p, q):
    def t(n):
        return n and (n.val, t(n.left), t(n.right))  
    return t(p) == t(q)

方法三：iteratively.

def isSameTree(self, p: 'TreeNode', q: 'TreeNode') -> 'bool':
    stack = [(p, q)]
    while stack:
        p1, p2 = stack.pop()
        if not p1 and not p2:
            continue
        if not p1 or not p2:
            return False
        if p1.val != p2.val:
            return False
        stack.append((p1.left, p2.left))
        stack.append((p1.right, p2.right))
    return True

101. Symmetric Tree

判断二叉树是否对称。原题

    1
   / \
  2   2
 / \ / \
3  4 4  3

方法一：recursively.

def isSymmetric(self, root: 'TreeNode') -> 'bool':

    def symmetric(p1, p2):
        if p1 and p2:
            return (p1.val == p2.val and symmetric(p1.left, p2.right) and 
                    symmetric(p1.right, p2.left))
        else:
            return p1 is p2

    if not root:
        return True
    return symmetric(root.left, root.right)

方法二：iteratively.

def isSymmetric(self, root: 'TreeNode') -> 'bool':
    stack = root and [(root.left, root.right)]        
    while stack:
        p1, p2 = stack.pop()
        if not p1 and not p2: continue
        if not p1 or not p2: return False
        if p1.val != p2.val: return False
        stack.append((p1.left, p2.right))
        stack.append((p1.right, p2.left))
    return True

104. Maximum Depth of Binary Tree

二叉树最大深度。原题

    3
   / \
  9  20
    /  \
   15   7
return 3

方法一：recursively

def max_depth(root):
    if not root:
        return 0
    return max(max_depth(root.left), max_depth(root.right)) + 1

方法二：iteratively. BFS with deque

def maxDepth(self, root: 'TreeNode') -> 'int':
    q = root and collections.deque([(root, 1)])
    d = 0
    while q:
        node, d = q.popleft()
        if node.right:
            q.append((node.right, d+1))
        if node.left:
            q.append((node.left, d+1))
    return d

可以参考102分层遍历写法，最后求长度。

559. Maximum Depth of N-ary Tree

N-叉树的最大深度。原题

方法一：BFS with deque.同上题一样。

def maxDepth(self, root: 'Node') -> 'int':
    q = root and collections.deque([(root, 1)])
    d = 0
    while q:
        node, d = q.popleft()
        for child in node.children:
            q.append((child, d + 1))
    return d

方法二：BFS.

def maxDepth(self, root):
    q, level = root and [root], 0
    while q:
        q, level = [child for node in q for child in node.children], level+1
    return level

方法三：recursively.

def maxDepth(self, root: 'Node') -> 'int':
    if not root:
        return 0
    return max(list(map(self.maxDepth, root.children)) or [0]) + 1

111. Minimum Depth of Binary Tree

求根节点到叶子节点的最小深度。原题

方法一：recursively

def minDepth(self, root):
    if not root:
        return 0
    if root.left and root.right:
        return min(self.minDepth(root.left), self.minDepth(root.right)) + 1
    else:
        return self.minDepth(root.left) + self.minDepth(root.right) + 1

方法二：对上述方法修改，更加Pythonic. 注意一点，Python3中要加list,否则max因为空值报错。

def minDepth(self, root: 'TreeNode') -> 'int':
    if not root: return 0
    d = list(map(self.minDepth, (root.left, root.right)))
    return 1 + (min(d) or max(d))

方法三：迭代法，BFS

def minDepth(self, root: 'TreeNode') -> 'int':
    q = root and collections.deque([(root, 1)])
    d = 0
    while q:
        node, d = q.popleft()
        if not node.left and not node.right:
            return d
        if node.left:
            q.append((node.left, d+1))
        if node.right:
            q.append((node.right, d+1))
    return d

105. Construct Binary Tree from Preorder and Inorder Traversal

根据前序遍历和中序遍历重建二叉树。原题

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

方法一：切片。

def buildTree(preorder, inorder):
    if preorder == []:
        return None
    root_val = preorder[0]
    root = TreeNode(root_val)
    cut = inorder.index(root_val)
    root.left = buildTree(preorder[1:cut+1], inorder[:cut])
    root.right = buildTree(preorder[cut+1:], inorder[cut+1:])
    return root

方法二：上述方法在极端情况下，如只有左子树的情况，由于index会将时间复杂度上升到O(n²)，而且切片产生了一些不必要的内存。这个方法是setefan大神的方法，pop和reverse是为了增加效率。

def buildTree(self, preorder: 'List[int]', inorder: 'List[int]') -> 'TreeNode':
    def build(stop):
        if inorder and inorder[-1] != stop:
            root = TreeNode(preorder.pop())
            root.left = build(root.val)
            inorder.pop()
            root.right = build(stop)
            return root
    preorder.reverse()
    inorder.reverse()
    return build(None)

106. Construct Binary Tree from Inorder and Postorder Traversal

根据中序遍历和后序遍历重建二叉树。原题

方法一：切片、

def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
    if not postorder:
        return None
    root_val = postorder[-1]
    root = TreeNode(root_val)
    cut = inorder.index(root_val)
    root.left = self.buildTree(inorder[:cut], postorder[:cut])
    root.right = self.buildTree(inorder[cut+1:], postorder[cut: -1])
    return root

方法二：stop pop的方式。甚至都不用reverse

def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
    def build(stop):
        if inorder and inorder[-1]!=stop:
            root = TreeNode(postorder.pop()) 
            root.right = build(root.val)
            inorder.pop()
            root.left  = build(stop)
            return root
         
    return build(None)

def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
    def build(stop, info='', lv=0):
        if inorder and inorder[-1]==stop:
            print('stop at', inorder, stop, info)
            return 
        print(lv*'->' , inorder, stop, postorder, info)
        if inorder and inorder[-1]!=stop:
            root = TreeNode(postorder.pop())
            root.right = build(root.val, "build {}'s right".format(root.val), lv+1)
            inorder.pop()
            root.left = build(stop, "build {}'s left".format(root.val), lv+1)
            return root

    return build(None)
  
[9, 3, 15, 20, 7] None [9, 15, 7, 20, 3] 
-> [9, 3, 15, 20, 7] 3 [9, 15, 7, 20] build 3's right
->-> [9, 3, 15, 20, 7] 20 [9, 15, 7] build 20's right
stop at [9, 3, 15, 20, 7] 7 build 7's right
stop at [9, 3, 15, 20] 20 build 7's left
->-> [9, 3, 15] 3 [9, 15] build 20's left
stop at [9, 3, 15] 15 build 15's right
stop at [9, 3] 3 build 15's left
-> [9] None [9] build 3's left
stop at [9] 9 build 9's right
->-> [] None [] build 9's left

889. Construct Binary Tree from Preorder and Postorder Traversal

根据前序和后序重建二叉树。原题

Input: pre = [1,2,4,5,3,6,7], post = [4,5,2,6,7,3,1]
Output: [1,2,3,4,5,6,7]

方法一：index的方式、、

def constructFromPrePost(self, pre: List[int], post: List[int]) -> TreeNode:
    if not post:
        return None
    root = TreeNode(post.pop())
    if len(pre) > 1:
        cut = post.index(pre[1])
        
        root.left = self.constructFromPrePost(pre[1:cut+2], post[:cut+1])
        root.right = self.constructFromPrePost(pre[cut+2:], post[cut+1:])
    return root

方法二：使用index递归 . by@lee215

class Solution:
    preIndex, posIndex = 0, 0
    def constructFromPrePost(self, pre, post):
        root = TreeNode(pre[self.preIndex])
        self.preIndex += 1
        if (root.val != post[self.posIndex]):
            root.left = self.constructFromPrePost(pre, post)
        if (root.val != post[self.posIndex]):
            root.right = self.constructFromPrePost(pre, post)
        self.posIndex += 1
        return root

572. Subtree of Another Tree

判断是否是树的子结构。原题

思路：这道题是遍历加判断相同树的结合。这里采用前序遍历和递归判断相同树。

def isSubtree(self, s: 'TreeNode', t: 'TreeNode') -> 'bool':

    def is_same(s, t):
        if s and t:
            return (s.val==t.val and is_same(s.left, t.left) and 
                    is_same(s.right, t.right))
        else:
            return s is t

    stack = s and [s]
    while stack:
        node = stack.pop()
        if node:
            if is_same(node, t):
                return True
            stack.append(node.right)
            stack.append(node.left)
    return False

方法二：生成器写法。

102. Binary Tree Level Order Traversal

分层遍历二叉树。原题

注意：循环条件要加上root，以防止root is None

def levelOrder(self, root: 'TreeNode') -> 'List[List[int]]':
    ans, level = [], root and [root]
    while level:
        ans.append([n.val for n in level])
        level = [k for n in level for k in (n.left, n.right) if k]
    return ans

103. Binary Tree Zigzag Level Order Traversal

之字形打印二叉树。原题

def zigzagLevelOrder(self, root: 'TreeNode') -> 'List[List[int]]':
    ans, level, order = [], root and [root], 1
    while level:
        ans.append([n.val for n in level][::order])
        order *= -1
        level = [kid for n in level for kid in (n.left, n.right) if kid]
    return ans

107. Binary Tree Level Order Traversal II

和102题不同的是，从下到上分层打印。原题

方法一：将结果倒序输出。

def levelOrderBottom(self, root):
    res, level = [], [root]
    while root and level:
        res.append([n.val for n in level])
        level = [kid for n in level for kid in (n.left, n.right) if kid]
    return res[::-1]

方法二：也可以从前面插入元素。

def levelOrderBottom(self, root):
    res, level = [], [root]
    while root and level:
        res.insert(0, [n.val for n in level])
        level = [kid for n in level for kid in (n.left, n.right) if kid]
    return res

429. N-ary Tree Level Order Traversal

分层打印N叉树。原题

def levelOrder(self, root: 'Node') -> 'List[List[int]]':
    ans, level = [], root and [root]
    while level:
        ans.append([n.val for n in level])
        level = [k for n in level for k in n.children if k]
    return ans

637. Average of Levels in Binary Tree

遍历一个二叉树，求每层节点的平均值，按照节点不为空的个数。原题

Input:
    3
   / \
  9  20
    /  \
   15   7
Output: [3, 14.5, 11]
Explanation:
The average value of nodes on level 0 is 3,  on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11].

def averageOfLevels(self, root: 'TreeNode') -> 'List[float]':
    ans, level = [], root and [root]
    while level:
        ans.append(sum(n.val for n in level) / len(level))
        level = [k for n in level for k in (n.left, n.right) if k]
    return ans

515. Find Largest Value in Each Tree Row

找到树每层的最大值。原题

方法一：BFS. 此解法秒。

def largestValues(self, root: TreeNode) -> List[int]:
    ans, levels = [], root and [root]
    while levels:
        ans.append(max(x.val for x in levels))
        levels = [k for n in levels for k in (n.left, n.right) if k]
    return ans

987. Vertical Order Traversal of a Binary Tree

垂直遍历二叉树，从左到右，从上到下，如果节点具有相同位置，按照值从小到大。原题

Input: [1,2,3,4,5,6,7]
Output: [[4],[2],[1,5,6],[3],[7]]
Explanation: 
The node with value 5 and the node with value 6 have the same position according to the given scheme.
However, in the report "[1,5,6]", the node value of 5 comes first since 5 is smaller than 6.

方法一：dfs. 通过建立一个字典数组，将对应的节点使用深度优先遍历初始化数组。然后按照x, y, val三个优先级进行排序。

def verticalTraversal(self, root: 'TreeNode') -> 'List[List[int]]':
    seen = collections.defaultdict(
        lambda: collections.defaultdict(list)
    )

    def dfs(node, x=0, y=0):
        if node:
            seen[x][y].append(node.val)
            dfs(node.left, x-1, y+1)
            dfs(node.right, x+1, y+1)

    dfs(root)
    ans = []
    for x in sorted(seen):
        inner = []
        for y in sorted(seen[x]):
            inner.extend(sorted(n for n in seen[x][y]))
        ans.append(inner)
    return ans

257. Binary Tree Paths

打印二叉树从根节点到叶子节点全部路径。原题

Input:

   1
 /   \
2     3
 \
  5

Output: ["1->2->5", "1->3"]

Explanation: All root-to-leaf paths are: 1->2->5, 1->3

iteratively。思路：采用前序遍历二叉树，使用tuple保存节点当前路径，如果是叶子节点，则添加到结果中。开始老是想着用'->'.join()，这样反而麻烦，直接使用字符串保存就好。

def binaryTreePaths(self, root: 'TreeNode') -> 'List[str]':
    ans, stack = [], root and [(root, str(root.val))]
    while stack:
        n, p = stack.pop()
        if not n.left and not n.right:
            ans.append(p)
        if n.right:
            stack.append((n.right, p+'->'+str(n.right.val)))
        if n.left:
            stack.append((n.left, p+'->'+str(n.left.val)))
    return ans

方法二：dfs.

def binaryTreePaths(self, root: 'TreeNode') -> 'List[str]':
    ans = []
    def dfs(n, path):
        if n:
            path.append(str(n.val))
            if not n.left and not n.right:
                ans.append('->'.join(path))
            dfs(n.left, path)
            dfs(n.right, path)
            path.pop()
    dfs(root, [])
    return ans

recursively。参考了StefanPochmann大神的方法。最开始想到一半，中间那层循环想到了，但没想到用递归。

def binaryTreePaths(self, root): 
    if not root:
        return []
    return [str(root.val) + '->' + path
            for kid in (root.left, root.right) if kid
            for path in self.binaryTreePaths(kid)] or [str(root.val)]

988. Smallest String Starting From Leaf

求字典顺序最小的路径，路径指叶子节点到根节点的路径。0对应a，1对应b。原题

Input: [0,1,2,3,4,3,4]
Output: "dba"

方法一：先列出所有根到叶子的路径，再reverse求最小值。

def smallestFromLeaf(self, root: 'TreeNode') -> 'str':
    OFFSET = ord('a')
    stack = root and [(root, chr(root.val+OFFSET))]
    ans = '~'
    while stack:
        n, p = stack.pop()
        if not n.left and not n.right:
            ans = min(ans, p[::-1])
        if n.right:
            stack.append((n.right, p+chr(n.right.val+OFFSET)))
        if n.left:
            stack.append((n.left, p+chr(n.left.val+OFFSET)))
    return ans

方法二：dfs. 递归计算完左右节点，然后再将根节点pop掉。

def smallestFromLeaf(self, root: 'TreeNode') -> 'str':
    self.ans = '~'
    
    def dfs(node, A):
        if node:
            A.append(chr(node.val + ord('a')))
            if not node.left and not node.right:
                self.ans = min(self.ans, ''.join(reversed(A)))
            dfs(node.left, A)
            dfs(node.right, A)
            A.pop()
        
    dfs(root, [])
    return self.ans

112. Path Sum

判断是否具有从根节点到叶子节点上的值和为sum。原题

方法一：recursively

def hasPathSum(self, root: 'TreeNode', total: 'int') -> 'bool':
    if not root:
        return False
    elif (not root.left and not root.right and 
        root.val==total):
        return True
    else:
        return (self.hasPathSum(root.left, total-root.val) or 
                self.hasPathSum(root.right, total-root.val))

方法二：iteratively

def hasPathSum(self, root: 'TreeNode', total: 'int') -> 'bool':
    stack = root and [(root, total)]
    while stack:
        n, t = stack.pop()
        if not n.left and not n.right and n.val==t:
            return True
        if n.right:
            stack.append((n.right, t-n.val))
        if n.left:
            stack.append((n.left, t-n.val))
    return False

113. Path Sum II

上题的升级版，要求二维数组返回所有路径。原题

sum = 22

      5
     / \
    4   8
   /   / \
  11  13  4
 /  \    / \
7    2  5   1

[
   [5,4,11,2],
   [5,8,4,5]
]

方法一：iteratively. 举一反三。

def pathSum(self, root: 'TreeNode', total: 'int') -> 'List[List[int]]':
    stack = root and [(root, [root.val], total)]
    ans = []
    while stack:
        n, v, t = stack.pop()
        if not n.left and not n.right and n.val==t:
            ans.append(v)
        if n.right:
            stack.append((n.right, v+[n.right.val], t-n.val))
        if n.left:
            stack.append((n.left, v+[n.left.val], t-n.val))
    return ans

recursively. 先找出所有路径，再过滤，实际上和257题一样。不过这并没有把这道题的特性涵盖进去。

def pathSum(self, root, sum_val):
    paths = self.all_paths(root)
    return [path for path in paths if sum(path)==sum_val]
    
def all_paths(self, root):
    if not root:
        return []
    return [[root.val]+path
            for kid in (root.left, root.right) if kid
            for path in self.all_paths(kid)] or [[root.val]]

方法三：recursively.

def pathSum(self, root, sum):
    if not root:
        return []
    val, *kids = root.val, root.left, root.right
    if any(kids):
        return [[val] + path
                for kid in kids if kid
                for path in self.pathSum(kid, sum-val)]
    return [[val]] if val==sum else []

方法四: dfs. 注意找到叶子节点后也要pop()。

def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
    self.ans = []

    def dfs(node, s, p):
        if not node: return
        p.append(node.val)
        s += node.val
        if not node.left and not node.right and s==sum:
            self.ans.append(p[:])
        else:
            dfs(node.left, s, p)
            dfs(node.right, s, p)
        p.pop()

    dfs(root, 0, [])
    return self.ans

297. Serialize and Deserialize Binary Tree

序列化反序列化二叉树。原题

class Codec:

    def serialize(self, root):
        if not root:
            return '$'
        return (str(root.val) + ',' + self.serialize(root.left) + 
                ',' + self.serialize(root.right))
        
    def deserialize(self, data):
        nodes = data.split(',')[::-1]
        return self.deserialize_tree(nodes)
    
    def deserialize_tree(self, nodes):
        val = nodes.pop()
        if val == '$':
            return None
        root = TreeNode(val)
        root.left = self.deserialize_tree(nodes)
        root.right = self.deserialize_tree(nodes)
        return root

110. Balanced Binary Tree

判断是否是平衡二叉树。原题

方法一：递归+递归。

def isBalanced(self, root):
    if not root:
        return True
    return self.isBalanced(root.left) and self.isBalanced(root.right) and \
           abs(self.max_depth(root.left)-self.max_depth(root.right)) <= 1
    
def max_depth(self, root):
    if not root:
        return 0
    return max(self.max_depth(root.left), self.max_depth(root.right)) + 1

方法二：上诉两种方法中都包含了一些无意义的重复遍历。这里采用后序遍历，边遍历边判断，不会重复节点。受此思想启发，添加一种后序遍历二叉树的方法。

def isBalanced(self, root):
    stack, node = [], root
    last, depths = None, collections.defaultdict(int)
    while stack or node:
        if node:
            stack.append(node)
            node = node.left
        else:
            node = stack[-1]
            if not node.right or last == node.right:
                node = stack.pop()
                left, right  = depths[node.left], depths[node.right]
                if abs(left - right) > 1: 
                    return False
                depths[node] = 1 + max(left, right)
                last, node = node, None
            else:
                node = node.right
    return True

方法三：dfs. 算深度的时候判断左右是否深度超过1. 这里变量不能把self去掉，否则[1,2,2,3,3,null,null,4,4]会错误的返回True而不是False。

def isBalanced(self, root: TreeNode) -> bool:
    self.balanced = True

    def dfs(node):
        if not node or not self.balanced:
            return 0
        left = dfs(node.left)
        right = dfs(node.right)
        if abs(left-right) > 1:
            self.balanced = False
        return max(left, right) + 1

    dfs(root)
    return self.balanced

108. Convert Sorted Array to Binary Search Tree

将有序数组转换成二叉搜索树。原题

Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5],
      0
     / \
   -3   9
   /   /
 -10  5

方法一：答案不唯一，居然一次就通过了。递归的思想还是简单一些的。

def sortedArrayToBST(self, nums):
    if not nums:
        return None
    mid = len(nums) // 2
    root = TreeNode(nums[mid])
    root.left = self.sortedArrayToBST(nums[:mid])
    root.right = self.sortedArrayToBST(nums[mid+1:])
    return root

方法二：不使用切片。

def sortedArrayToBST(self, nums: 'List[int]') -> 'TreeNode':
    
    def convert(lo, hi):
        if lo > hi:
            return None
        mid = (lo+hi) // 2
        root = TreeNode(nums[mid])
        root.left = convert(lo, mid-1)
        root.right = convert(mid+1, hi)
        return root

    return convert(0, len(nums)-1)

235. Lowest Common Ancestor of a Binary Search Tree

寻找二叉搜索树的最小公共祖先。原题

方法一：iteratively.

def lowestCommonAncestor(self, root, p, q):
    while (root.val-p.val) * (root.val-q.val) > 0:
        root = (root.left, root.right)[root.val < p.val]
    return root

方法二：recursively.

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    if (root.val-p.val) * (root.val-q.val) <= 0:
        return root
    return self.lowestCommonAncestor(
        (root.left, root.right)[root.val < p.val], p, q)

404. Sum of Left Leaves

求一个二叉树所有左叶子节点的和。原题

方法一：iteratively.这里使用了tuple记录是否为左叶子节点。

def sumOfLeftLeaves(self, root: 'TreeNode') -> 'int':
    ans, stack = 0, root and [(root, False)]
    while stack:
        n, isleft = stack.pop()
        if n:
            if not n.left and not n.right and isleft:
                ans += n.val
            stack.append((n.right, False))
            stack.append((n.left, True))
    return ans

方法二：recursively.

def sumOfLeftLeaves(self, root: 'TreeNode') -> 'int':
    if not root:
        return 0
    if (root.left and not root.left.left and not root.left.right):
        return root.left.val + self.sumOfLeftLeaves(root.right)
    else:
        return (self.sumOfLeftLeaves(root.left) + 
                self.sumOfLeftLeaves(root.right))

938. Range Sum of BST

给两个节点的值，求二叉搜索树在这两个值之间的节点和。每个节点的值唯一。原题

Input: root = [10,5,15,3,7,null,18], L = 7, R = 15
Output: 32
Input: root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
Output: 23

方法一：因为是竞赛题，所以没追求效率，所以这里先前序遍历了一下，再根据条件求和。

def rangeSumBST(self, root, L, R):
    traverse, stack = [], [root]
    while stack:
        node = stack.pop()
        if node:
            traverse.append(node.val)
            if node.right:
                stack.append(node.right)
            if node.left:
                stack.append(node.left)
    return sum([x for x in traverse if L <= x <= R])

方法二：利用二叉搜索树的特性。

def rangeSumBST(self, root: 'TreeNode', L: 'int', R: 'int') -> 'int':
    ans, stack = 0, root and [root]
    while stack:
        node = stack.pop()
        if node.val > L and node.left:
            stack.append(node.left)
        if node.val < R and node.right:
            stack.append(node.right)
        if L <= node.val <= R:
            ans += node.val
    return ans

方法三：递归。

def rangeSumBST(self, root: TreeNode, low: int, high: int) -> int:
    ans = 0
    if root:
        if low <= root.val <= high:
            ans += root.val
            ans += self.rangeSumBST(root.left, low, high)
            ans += self.rangeSumBST(root.right, low, high)
        elif root.val < low:
            ans += self.rangeSumBST(root.right, low, high)
        else:
            ans += self.rangeSumBST(root.left, low, high)
    return ans

530. Minimum Absolute Difference in BST

求二叉搜索树任意两个节点的最小差。原题

Input:

   1
    \
     3
    /
   2

Output:
1

Explanation:
The minimum absolute difference is 1, which is the difference between 2 and 1 (or between 2 and 3).

def getMinimumDifference(self, root: 'TreeNode') -> 'int':

    def inorder(n):
        if not n:
            return []
        return inorder(n.left) + [n.val] + inorder(n.right)

    nums = inorder(root)
    # return min(nums[i+1]-nums[i] for i in range(len(nums)-1))
    return min(b-a for a, b in zip(nums, nums[1:]))

783. Minimum Distance Between BST Nodes

二叉搜索树两个节点的最小值。和530是一道题。原题

Input: root = [4,2,6,1,3,null,null]
Output: 1
Explanation:
Note that root is a TreeNode object, not an array.

The given tree [4,2,6,1,3,null,null] is represented by the following diagram:

          4
        /   \
      2      6
     / \    
    1   3  

while the minimum difference in this tree is 1, it occurs between node 1 and node 2, also between node 3 and node 2.

方法一：递归 + 生成器， 遍历了两次。

def minDiffInBST(self, root: 'TreeNode') -> 'int':
    
    def inorder(node):
        if not node:
            return []
        return inorder(node.left) + [node.val] + inorder(node.right)
    
    t = inorder(root)
    return min(t[x]-t[x-1] for x in range(1, len(t)))

方法二：一次遍历，没有保存整个遍历数组，效率高。

def minDiffInBST(self, root: TreeNode) -> int:
    ans, last, stack = float('inf'), float('-inf'), []
    while stack or root:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        ans, last = min(ans, root.val-last), root.val
        root = root.right
    return ans

方法三：一次递归。

class Solution:
    pre = float('-inf')
    ans = float('inf')
    
    def minDiffInBST(self, root: 'TreeNode') -> 'int':
        if root.left:
            self.minDiffInBST(root.left)
        self.ans = min(self.ans, root.val-self.pre)
        self.pre = root.val
        if root.right:
            self.minDiffInBST(root.right)
        return self.ans

538. Convert BST to Greater Tree

二叉搜索树转换。使得节点的值等于所有比它大的节点的和。原题

Input: The root of a Binary Search Tree like this:
              5
            /   \
           2     13

Output: The root of a Greater Tree like this:
             18
            /   \
          20     13

方法一：recursively。这里使用了一个变量来保存当前的累加和，然后递归中采用先右后左的方式。

def convertBST(self, root: TreeNode) -> TreeNode:   
    self.val = 0

    def dfs(node):
        if node:
            dfs(node.right)
            self.val += node.val
            node.val = self.val
            dfs(node.left)

    dfs(root)
    return root

方法二：iteratively。

def convertBST(self, root: TreeNode) -> TreeNode:   
    head = root
    stack, val = [], 0
    while stack or root:
        while root:
            stack.append(root)
            root = root.right
        root = stack.pop()
        val += root.val
        root.val = val
        root = root.left
    return head

方法三：生成器写法。

def convertBST(self, root: TreeNode) -> TreeNode:   

    def dfs(node):
        if node:
            yield from dfs(node.right)
            yield node
            yield from dfs(node.left)
    val = 0
    for node in dfs(root):
        val += node.val
        node.val = val
    return root

958. Check Completeness of a Binary Tree

判断二叉树是否是完整二叉树。完整二叉树为：除了最后一层所有节点不能为空，最后一层节点全部去靠左。原题

Example 1:

Input: [1,2,3,4,5,6]
Output: true
Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.

Example 2:

Input: [1,2,3,4,5,null,7]
Output: false
Explanation: The node with value 7 isn't as far left as possible.

方法一：采用分层遍历的方式，判断每层的节点是否是2**level。最后一层采用切片的方式判断最左原则。

class Solution:
    def isCompleteTree(self, root):
        if not root:
            return True
        levels = [root]
        last_full = True
        level = 0
        while levels:
            value_nodes = [n for n in levels if n]
            if value_nodes != levels[:len(value_nodes)]:
                return False
            else:
                print(len(levels), 2**level)
                if len(levels) != 2**level:
                    if not last_full:
                        return False
                    last_full = False
                
            levels = [kid for n in levels if n for kid in (n.left, n.right)]
            level += 1
        return True

方法二：Lee神的写法，想明白一件事就是，遇见第一个None时，后面如果再有非None的值就不是玩整树了。

def isCompleteTree(self, root: 'TreeNode') -> 'bool':
    i, bfs = 0, [root]
    while bfs[i]:
        bfs.append(bfs[i].left)
        bfs.append(bfs[i].right)
        i += 1
    return not any(bfs[i:])

543. Diameter of Binary Tree

求二叉树的最大直径，即任意两节点的长度。原题

          1
         / \
        2   3
       / \     
      4   5    
Return **3**, which is the length of the path [4,2,1,3] or [5,2,1,3].

方法一： recursively, 使用一个实例变量计算了最大值。

def diameterOfBinaryTree(self, root: 'TreeNode') -> 'int':
    self.diameter = 0

    def dfs(node):
        if not node:
            return 0
        left = dfs(node.left)
        right = dfs(node.right)
        self.diameter = max(self.diameter, left+right)
        return max(left, right) + 1

    dfs(root)
    return self.diameter

965. Univalued Binary Tree

判断一个二叉树是否所有节点具有相同的值。原题

方法一：recursively。

def isUnivalTree(self, root: 'TreeNode') -> 'bool':
    def dfs(node):
        return (not node or root.val==node.val and 
                dfs(node.left) and dfs(node.right))
    return dfs(root)

方法二：iteratively.常规写法。

def isUnivalTree(self, root: 'TreeNode') -> 'bool':
    r_val, stack = root.val, [root]
    while stack:
        n = stack.pop()
        if n:
            if n.val != r_val:
                return False
            stack.append(n.right)
            stack.append(n.left)
    return True

方法二：前序遍历，生成器方法。

def isUnivalTree(self, root: 'TreeNode') -> 'bool':
    
    def bfs(node):
        if node:
            yield node.val
            yield from bfs(node.left)
            yield from bfs(node.right)
            
    it = bfs(root)
    root_val = next(it)
    for val in it:
        if val != root_val:
            return False
    return True

563. Binary Tree Tilt

返回一个二叉树整个树的倾斜度。所有节点倾斜度的总和。节点的倾斜度等于左子树和右子树所有和差的绝对值。原题

Input: 
         1
       /   \
      2     3
Output: 1
Explanation: 
Tilt of node 2 : 0
Tilt of node 3 : 0
Tilt of node 1 : |2-3| = 1
Tilt of binary tree : 0 + 0 + 1 = 1

方法一：recursively. 这里用tuple记录了节点总和和倾斜度总和。

def findTilt(self, root):
    self.res = 0
    _, top_res = self.sum_and_diff(root)
    return self.res + top_res

def sum_and_diff(self, node):
    if not node:
        return 0, 0
    l_sum, l_diff = self.sum_and_diff(node.left)
    r_sum, r_diff = self.sum_and_diff(node.right)
    self.res += l_diff + r_diff
    # print(node.val, node.val+l_sum+r_sum, abs(l_sum-r_sum))
    return node.val+l_sum+r_sum, abs(l_sum-r_sum)

方法二: 想了一会后序遍历的迭代法，没想出来，貌似需要维护很多的变量。这里还是优化一下方法一。

def findTilt(self, root: 'TreeNode') -> 'int':

    def dfs(node):
        if not node:
            return 0, 0
        l_sum, l_diff = dfs(node.left)
        r_sum, r_diff = dfs(node.right)
        return (node.val + l_sum + r_sum, 
                abs(l_sum-r_sum) + l_diff + r_diff)

    return dfs(root)[1]

606. Construct String from Binary Tree

根据二叉树重建字符串，使用()表示嵌套关系。原题

Input: Binary tree: [1,2,3,4]
       1
     /   \
    2     3
   /    
  4     
Output: "1(2(4))(3)"

Input: Binary tree: [1,2,3,null,4]
       1
     /   \
    2     3
     \  
      4 
Output: "1(2()(4))(3)"

方法一：recursively. 左右节点有一点区别，在于如果左节点为空，右节点不为空，要保留左节点的括号。

def tree2str(self, t):
    if not t: return ''
    left = '({})'.format(self.tree2str(t.left)) if (t.left or t.right) else ''
    right = '({})'.format(self.tree2str(t.right)) if t.right else ''
    return '{}{}{}'.format(t.val, left, right)

617. Merge Two Binary Trees

合并两个二叉树，相同位置的节点值相加，空节点算0.原题

方法一：recursively.

def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
    if not t1 and not t2:
        return None
    v1, v2 = t1.val if t1 else 0, t2.val if t2 else 0
    root = TreeNode(v1+v2)
    root.left = self.mergeTrees(t1.left if t1 else None, t2.left if t2 else None)
    root.right = self.mergeTrees(t1.right if t1 else None, t2.right if t2 else None)
    return root

方法二：iteratively.

def mergeTrees(self, t1, t2):
    if not t1 and not t2:
        return []
    t = TreeNode(0)
    stack = [(t, t1, t2)]
    while stack:
        n, n1, n2 = stack.pop()
        if n1 or n2:
            n.val = (n1.val if n1 else 0) + (n2.val if n2 else 0)
            if (n1 and n1.right) or (n2 and n2.right):
                n.right = TreeNode(None)
                stack.append((n.right, n1.right if n1 else None, n2.right if n2 else None))
            if (n1 and n1.left) or (n2 and n2.left):
                n.left = TreeNode(None)
                stack.append((n.left, n1.left if n1 else None, n2.left if n2 else None))
    return t

653. Two Sum IV - Input is a BST

判断二叉树中是否有两个节点相加为k。原题

Input: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 9

Output: True

方法一：preorder + set.

def findTarget(self, root, k):
    seen, stack = set(), root and [root]
    while stack:
        node = stack.pop()
        if node:
            if k-node.val in seen:
                return True
            seen.add(node.val)
            stack.append(node.right)
            stack.append(node.left)
    return False

669. Trim a Binary Search Tree

根据范围修剪二叉搜索树，注意是二叉搜索树，不是普通的二叉树。原题

Input: 
    1
   / \
  0   2

  L = 1
  R = 2

Output: 
    1
      \
       2

方法一：recursively.

def trimBST(self, root, L, R):
    def trim_node(node):
        if not node:
            return None
        elif node.val > R:
            return trim_node(node.left)
        elif node.val < L:
            return trim_node(node.right)
        else:
            node.left = trim_node(node.left)
            node.right = trim_node(node.right)
            return node
    return trim_node(root)

671. Second Minimum Node In a Binary Tree

找出二叉树中第二小的节点值。左右子节点同时存在或同时不存在，根节点小于等于任意子节点。原题

Input: 
    2
   / \
  2   5
     / \
    5   7

Output: 5
Explanation: The smallest value is 2, the second smallest value is 5.

方法一：先放到set里.

def findSecondMinimumValue(self, root: 'TreeNode') -> 'int':
    self.uniques = set()

    def dfs(node):
        if node:
            self.uniques.add(node.val)
            dfs(node.left)
            dfs(node.right)

    dfs(root)
    min1, ans = root.val, float('inf')
    for v in self.uniques:
        if min1 < v < ans:
            ans = v
    return ans if ans < float('inf') else -1

方法二： iteratively.

def findSecondMinimumValue(self, root):
    min1 = root.val if root else -1
    res = float('inf')
    stack = root and [root]
    while stack:
        node = stack.pop()
        if node:
            if min1 < node.val < res:
                res = node.val
            stack.extend([node.right, node.left])
    return res if res < float('inf') else -1

方法三：还没想出来，以上两种都没有利用到一些题中已知条件，我看Solution中给出的及一些Discuss中的答案也忽略了这个条件。想了想无论是哪个顺序遍历，或者深度广度优先，都没能很好的利用这个条件。

687. Longest Univalue Path

相同节点最长路径，路径长度按照两个节点之间的边距，也就是节点数-1。原题

              5
             / \
            4   5
           / \   \
          1   1   5
output: 2

def longestUnivaluePath(self, root):
    self.res = 0
    def traverse(node):
        if not node:
            return 0
        left_len, right_len = traverse(node.left), traverse(node.right)
        left = (left_len+1) if node.left and node.left.val==node.val else 0
        right = (right_len+1) if node.right and node.right.val==node.val else 0
        self.res = max(self.res, left + right)
        return max(left, right)
    traverse(root)
    return self.res

700. Search in a Binary Search Tree

在二叉搜索树中搜索节点。原题

Given the tree:
        4
       / \
      2   7
     / \
    1   3

And the value to search: 2

方法一：recursively.

def searchBST(self, root: 'TreeNode', val: 'int') -> 'TreeNode':
    if root:
        if val == root.val:
            return root
        return self.searchBST(
            (root.left, root.right)[root.val < val], val)

方法二：iteratively.

def searchBST(self, root: 'TreeNode', val: 'int') -> 'TreeNode':
    node = root
    while node and node.val != val:
        node = (node.left, node.right)[node.val < val]
    return node

872. Leaf-Similar Trees

叶子相近的树，只从左到右遍历叶子节点的顺序相同的两棵树。原题

方法一：前序遍历+生成器。空间复杂度过高，beats 1%。

def leafSimilar(self, root1: 'TreeNode', root2: 'TreeNode') -> 'bool':

    def leaves(root):
        stack = root and [root]
        while stack:
            node = stack.pop()
            if node:
                if not node.right and not node.left:
                    yield node.val
                stack.append(node.right)
                stack.append(node.left)

    leaves1 = leaves(root1)
    leaves2 = leaves(root2)
    return all(
        a==b for a, b in itertools.zip_longest(leaves1, leaves2))

方法二：dfs.

def leafSimilar(self, root1: 'TreeNode', root2: 'TreeNode') -> 'bool':

    def dfs(node):
        if node:
            if not node.left and not node.right:
                yield node.val
            yield from dfs(node.left)
            yield from dfs(node.right)

    return all(
        a==b for a, b in itertools.zip_longest(dfs(root1), dfs(root2)))

897. Increasing Order Search Tree

根据中序遍历建立一个只有右子树的二叉树。要求在原树上修改。原题

Example 1:
Input: [5,3,6,2,4,null,8,1,null,null,null,7,9]

       5
      / \
    3    6
   / \    \
  2   4    8
 /        / \ 
1        7   9

Output: [1,null,2,null,3,null,4,null,5,null,6,null,7,null,8,null,9]

 1
  \
   2
    \
     3
      \
       4

方法一：iteratively.

def increasingBST(self, root: TreeNode) -> TreeNode:
    ans = head = TreeNode(0)
    stack = []
    while stack or root:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        head.right = TreeNode(root.val)
        root, head = root.right, head.right
    return ans.right

方法二：生成器。

def increasingBST(self, root: 'TreeNode') -> 'TreeNode':
    
    def inorder(node):
        if node:
            yield from inorder(node.left)
            yield node.val
            yield from inorder(node.right)
            
    ans = head = TreeNode(0)
    for v in inorder(root):
        head.right = TreeNode(v)
        head = head.right
    return ans.right

方法三：题中有个要求在原树上修改，所以以上两种方法其实不符合要求，这里使用递归实现。 此答案由lee大神提供，非常巧妙。

def increasingBST(self, root: 'TreeNode', tail=None) -> 'TreeNode':
    if not root: return tail
    res = self.increasingBST(root.left, root)
    root.left = None
    root.right = self.increasingBST(root.right, tail)
    return res

993. Cousins in Binary Tree

表弟节点指两个节点在同一深度，并且父节点不同。判断两个节点是否是表弟节点。树中节点值唯一。原题

方法一：用dict记录。

def isCousins(self, root: 'TreeNode', x: 'int', y: 'int') -> 'bool':
    parent, depth = {}, {}
    
    def dfs(node, par=None):
        if node:
            parent[node.val] = par
            depth[node.val] = depth[par] + 1 if par else 0
            dfs(node.left, node.val)
            dfs(node.right, node.val)
            
    dfs(root)
    return depth[x] == depth[y] and parent[x] != parent[y]

230. Kth Smallest Element in a BST

二叉搜索树的第K小节点值。原题

Input: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
Output: 1

方法一：生成器前序遍历。

def kthSmallest(self, root: TreeNode, k: int) -> int:
    
    def inorder(node):
        if node:
            yield from inorder(node.left)
            yield node.val
            yield from inorder(node.right)
            
    for n in inorder(root):
        if k == 1:
            return n
        else:
            k -= 1

方法二：迭代。

def kthSmallest(self, root: TreeNode, k: int) -> int:
    stack = []
    while root or stack:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        k -= 1
        if k == 0:
            return root.val
        root = root.right

98. Validate Binary Search Tree

验证一个树是否是二叉搜索树。原题

    5
   / \
  1   4
     / \
    3   6
Output: false
Explanation: The input is: [5,1,4,null,null,3,6]. The root node's value
             is 5 but its right child's value is 4.

方法一：中序遍历即可。

def isValidBST(self, root: TreeNode) -> bool:
    stack, last = [], float('-inf')
    while stack or root:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        if root.val <= last:
            return False
        last = root.val
        root = root.right
    return True

方法二：整个活。

def isValidBST(self, root: TreeNode) -> bool:

    def inorder(node):
        if node:
            yield from inorder(node.left)
            yield node.val
            yield from inorder(node.right)

    a, b = itertools.tee(inorder(root))
    next(b, None)
    return all(c < d for c, d in zip(a, b))

109. Convert Sorted List to Binary Search Tree

将有序链表转成平衡二叉搜索树。原题

Given the sorted linked list: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

方法一：先遍历链表，再二分递归创建树。

def sortedListToBST(self, head: ListNode) -> TreeNode:
    inorder = []
    while head:
        inorder.append(head.val)
        head = head.next
    lo, hi = 0, len(inorder)-1
    
    def build_tree(lo, hi):
        if lo > hi:
            return None
        mid = (lo + hi) // 2
        root = TreeNode(inorder[mid])
        root.left = build_tree(lo, mid-1)
        root.right = build_tree(mid+1, hi)
        return root
        
    return build_tree(lo, hi)

方法二：这个方法很棒。先遍历一遍找到链表的长度；然后递归去构建树，共享一个head可变对象。

def sortedListToBST(self, head: ListNode) -> TreeNode:
    
    def find_size(head):
        h, count = head, 0
        while h:
            h = h.next
            count += 1
        return count
    lo, hi = 0, find_size(head)
    
    def form_bst(lo, hi):
        nonlocal head
        if lo > hi:
            return None
        mid = (lo + hi) // 2
        left = form_bst(lo, mid-1)
        root = TreeNode(head.val)
        head = head.next
        root.left = left
        right = form_bst(mid+1, hi)
        root.right = right
        return root
    
    return form_bst(lo, hi-1)

1008. Construct Binary Search Tree from Preorder Traversal

根据前序遍历重建二叉搜索树。原题

Input: [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]

方法一：recursively.

def bstFromPreorder(self, preorder: List[int]) -> TreeNode:
    if not preorder: return None
    root = TreeNode(preorder[0])
    i = bisect.bisect(preorder, root.val)
    root.left = self.bstFromPreorder(preorder[1:i])
    root.right = self.bstFromPreorder(preorder[i:])
    return root

236. Lowest Common Ancestor of a Binary Tree

二叉树两个节点的最小公共祖先。原题

方法一: 递归，是用mid表示当前节点是否是其中的一个。

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    self.ans = None
    
    def dfs(node):
        if not node:
            return False
        left = dfs(node.left)
        right = dfs(node.right)
        mid = node in (p, q)
        if mid + left + right >= 2:
            self.ans = node
        return mid or left or right
    dfs(root)
    return self.ans

方法二：递归，思想如果是两个节点中的一个，就返回这个节点。

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    if root in (None, p, q):
        return root
    left = self.lowestCommonAncestor(root.left, p, q)
    right = self.lowestCommonAncestor(root.right, p, q)
    return root if left and right else left or right

方法三：参考了257的dfs解法。需要注意的是一定要加list(path)，否则由于可变对象的问题，会导致最后结果为[]。

def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
    ans = []
    def dfs(n, path):
        if n:
            path.append(n)
            if n in (p, q):
                ans.append(list(path))   # must use list, or you will get []
                if len(ans) == 2:		 # optimized
                    return 
            dfs(n.left, path)
            dfs(n.right, path)
            path.pop()
    dfs(root, [])
    return next(a for a, b in list(zip(*ans))[::-1] if a==b)

654. Maximum Binary Tree

根据数组建立一个树，要求根节点为数组最大的树。原题

方法一：此题秒，不过感觉还有更优解，查了一圈没找到。

def constructMaximumBinaryTree(self, nums: List[int]) -> TreeNode:
    if not nums:
        return None
    v = max(nums)
    root = TreeNode(v)
    i = nums.index(v)
    root.left = self.constructMaximumBinaryTree(nums[:i])
    root.right = self.constructMaximumBinaryTree(nums[i+1:])
    return root

513. Find Bottom Left Tree Value

寻找二叉树最底层的最左节点。原题

方法一：根据分层遍历改编。

def findBottomLeftValue(self, root: TreeNode) -> int:
    ans, levels = None, root and [root]
    while levels:
        ans = levels[0].val
        levels = [k for n in levels for k in (n.left, n.right) if k]
    return ans

方法二：双端队列，BFS.

def findBottomLeftValue(self, root: TreeNode) -> int:
    q = collections.deque([root])
    while q:
        node = q.pop()
        if node.right:
            q.appendleft(node.right)
        if node.left:
            q.appendleft(node.left)
    return node.val

方法三：循环时改变迭代对象，这种方式个人觉得不好。不过好在是在遍历之前添加到末端。

def findBottomLeftValue(self, root: TreeNode) -> int:
    queue = [root]
    for node in queue:
        queue += (x for x in (node.right, node.left) if x)
    return node.val

814. Binary Tree Pruning

剪掉树中不包含1的子树。原题

方法一：递归。

def pruneTree(self, root: TreeNode) -> TreeNode:
    
    def dfs(node):
        if not node:
            return True
        left = dfs(node.left)
        right = dfs(node.right)
        if left:
            node.left = None
        if right:
            node.right = None
        
        return node.val==0 and left and right
    dfs(root)
    return root

199. Binary Tree Right Side View

二叉树从右向左看时，从上到下的节点。原题

方法一：和分层遍历思想相同。

def rightSideView(self, root: TreeNode) -> List[int]:
    ans, levels = [], root and [root]
    while levels:
        ans.append(levels[-1].val)
        levels = [k for n in levels for k in (n.left, n.right) if k]
    return ans

方法二：dfs. 从右到左深度遍历，用一个深度变量控制是否是第一个最右节点。

def rightSideView(self, root: TreeNode) -> List[int]:
    ans = []
    def dfs(n, depth):
        if n:
            if depth == len(ans):
                ans.append(n.val)
            dfs(n.right, depth+1)
            dfs(n.left, depth+1)
    dfs(root, 0)
    return ans

662. Maximum Width of Binary Tree

二叉树的最大宽度。原题

方法一：常规队列写法。需要注意的是，每层遍历要用最右边的减去最左边的才是宽度。

def widthOfBinaryTree(self, root: TreeNode) -> int:
    queue = [(root, 0, 0)]
    ans = cur_depth = left = 0
    for node, depth, pos in queue:
        if node:
            queue.append((node.left, depth+1, pos*2))
            queue.append((node.right, depth+1, pos*2+1))
            if cur_depth != depth:
                cur_depth = depth
                left = pos
            ans = max(pos-left+1, ans)
    return ans

方法二：按照分层顺序将所有节点编号，从1开始，enumerate其实就是计算2*pos, 2*pos+1。

def widthOfBinaryTree(self, root: TreeNode) -> int:
    levels = [(1, root)]
    width = 0
    while levels:
        width = max(levels[-1][0] - levels[0][0] + 1, width)
        levels = [k
                  for pos, n in levels
                  for k in enumerate((n.left, n.right), 2 * pos)
                  if k[1]]
    return width

222. Count Complete Tree Nodes

统计完整树的节点个数。原题

方法一：二分法。比较左子树的深度和右子树的深度，如果相同则表明左子树为满树，右子树为完整树。如果不同则表明左子树为完整树，右子树为满树。

def countNodes(self, root: TreeNode) -> int:
    if not root:
        return 0
    left, right = self.depth(root.left), self.depth(root.right)
    if left == right:
        return 2 ** left + self.countNodes(root.right)
    else:
        return 2 ** right + self.countNodes(root.left)
    
def depth(self, node):
    if not node:
        return 0
    return 1 + self.depth(node.left)

1022. Sum of Root To Leaf Binary Numbers

计算所有根到叶子节点路径二进制数表示的的和。原题

Input: [1,0,1,0,1,0,1]
Output: 22
Explanation: (100) + (101) + (110) + (111) = 4 + 5 + 6 + 7 = 22

思路和 257.Binary Tree Paths一样。

def sumRootToLeaf(self, root: TreeNode) -> int:
    self.ans = 0
    def dfs(n, path):
        if n:
            path.append(str(n.val))
            if not n.left and not n.right:
                self.ans += int(''.join(path), 2)
            dfs(n.left, path)
            dfs(n.right, path)
            path.pop()
            
    dfs(root, [])
    return self.ans % (10**9 + 7)

1026. Maximum Difference Between Node and Ancestor

祖先和其子节点的最大差绝对值。原题

方法一：周赛时写的dfs. 380ms. 瓶颈在于每次都求一次最大值和最小值。

def maxAncestorDiff(self, root: TreeNode) -> int:
    self.ans = float('-inf')
    
    def dfs(n, p):
        if n:
            if p:
                max_diff = max(abs(max(p)-n.val), abs(min(p)-n.val))
                self.ans = max(self.ans, max_diff)
            p.append(n.val)
            dfs(n.left, p)
            dfs(n.right, p)
            p.pop()
    
    dfs(root, [])
    return self.ans

方法二：改良了一下，使用p记录一个当前的最大值和最小值。52ms.

def maxAncestorDiff(self, root: TreeNode) -> int:
    self.ans = float('-inf')
    
    def dfs(n, p):
        if n:
            if p:
                mx, mn = p[-1]
                self.ans = max(self.ans, max(mx-n.val, n.val-mn))
                p.append((max(mx, n.val), min(mn, n.val)))
            else:
                p.append((n.val, n.val))
            dfs(n.left, p)
            dfs(n.right, p)
            p.pop() 
    dfs(root, [])
    return self.ans

1038. Binary Search Tree to Greater Sum Tree

二叉搜索树转成一颗规则的树，从右根左的顺序累加节点值。原题

方法一：使用栈。

def bstToGst(self, root: TreeNode) -> TreeNode:
    head = root
    stack, total = [], 0
    while stack or root:
        while root:
            stack.append(root)
            root = root.right
        root = stack.pop()
        total += root.val
        root.val = total
        root = root.left
    return head

方法二：Lee神的递归方式。

class Solution:
    val = 0
    def bstToGst(self, root: TreeNode) -> TreeNode:
        if root.right: self.bstToGst(root.right)
        root.val = self.val = self.val + root.val
        if root.left: self.bstToGst(root.left)
        return root

1080. Insufficient Nodes in Root to Leaf Paths

计算所有的根到叶子节点的路径，如果路径和小于给定值，则剪掉这个树枝。原题

方法一：递归。

def sufficientSubset(self, root: TreeNode, limit: int) -> TreeNode:
    if not root:
        return None
    if not root.left and not root.right:
        return root if root.val >= limit else None
    root.left = self.sufficientSubset(root.left, limit-root.val)
    root.right = self.sufficientSubset(root.right, limit-root.val)
    return root if root.left or root.right else None

1161. Maximum Level Sum of a Binary Tree

求最节点和最大层的层数。原题

方法一：分层遍历

def maxLevelSum(self, root: TreeNode) -> int:
    lvsum = []
    level = [root]
    while level:
        lvsum.append(sum(n.val for n in level))
        level = [k for n in level for k in (n.left, n.right) if k]
    return lvsum.index(max(lvsum)) + 1

1104. Path In Zigzag Labelled Binary Tree

之字形树的目标节点路径。原题

方法一：迭代，此题纯粹是数学题，这里先假设非之字形的树，找到规律，然后知道每层的节点数再相减。

def pathInZigZagTree(self, label: int) -> List[int]:
    
    ans = []
    n = 0
    while 2 ** n <= label:
        n += 1
    
    while n > 0 and label >= 1:
        ans.append(label)
        org_lable = label // 2
        label = 2**(n-1)-1-org_lable+2**(n-2)
        n -= 1
    return ans[::-1]

方法二：Lee神的递归。原理一样，层数n是通过查2的幂求的。

def pathInZigZagTree(self, x):
    return self.pathInZigZagTree(3 * 2 ** (len(bin(x)) - 4) - 1 - x / 2) + [x] if x > 1 else [1]

1110. Delete Nodes And Return Forest

给定一个树，删除指定的一些节点，然后删除的节点的左右子树成为单独的根节点。返回所有的树。原题

Input: root = [1,2,3,4,5,6,7], to_delete = [3,5]
Output: [[1,2,null,4],[6],[7]]

方法一：递归。做着题的时候有个误区：在当前节点被删除后，找到其在父节点对应的位置，然后置为空。实际上应该讲根节点删除的状态保留，在下一层处理。

def delNodes(self, root: TreeNode, to_delete: List[int]) -> List[TreeNode]:
    ans = []
    to_del = set(to_delete)
    
    def helper(root, is_root):
        
        if not root:
            return None
        is_del = root.val in to_del
        root.left = helper(root.left, is_del)
        root.right = helper(root.right, is_del)
        if not is_del and is_root:
            ans.append(root)
        return None if is_del else root
    
    helper(root, True)
    return ans

1123. Lowest Common Ancestor of Deepest Leaves

最深的叶子节点的最小公共祖先。原题

Input: root = [1,2,3]
Output: [1,2,3]
Explanation: 
The deepest leaves are the nodes with values 2 and 3.
The lowest common ancestor of these leaves is the node with value 1.
The answer returned is a TreeNode object (not an array) with serialization "[1,2,3]".

方法一：Lee神的方法比我的好太多，我借鉴了之前的dfs的方式遍历所有的path，然后再清洗比较。其实直接递归即可。

def lcaDeepestLeaves(self, root: TreeNode) -> TreeNode:
    
    def helper(root):
        if not root:
            return 0, None
        d1, n1 = helper(root.left)
        d2, n2 = helper(root.right)
        if d1 < d2:
            return d2 + 1, n2
        elif d1 > d2:
            return d1 + 1, n1
        else:
            return d1 + 1, root
        
    return helper(root)[1]

1382. Balance a Binary Search Tree

将一个二叉搜索树转为平衡二叉搜索树。原题

方法一：想到二叉搜索树首先想到中序遍历，所以一共分为2步，一步是遍历出所有节点，再根据节点重建一个平衡的二叉搜索树。

class Solution:
    def balanceBST(self, root: TreeNode) -> TreeNode:
        
        def dfs(node):
            if node:
                yield from dfs(node.left)
                yield node.val
                yield from dfs(node.right)
        
        inorder = list(dfs(root))
    
        def build(inorder):
            if not inorder:
                return None
            n = len(inorder)
            index = n // 2
            root = TreeNode(inorder[index])
            root.left = build(inorder[:index])
            root.right = build(inorder[index+1:])
            return root
        
        return build(inorder)

1372. Longest ZigZag Path in a Binary Tree

二叉树中最长的z字形路径。原题

方法一：用了不少变量来控制走位。

def longestZigZag(self, root: TreeNode) -> int:
    self.ans = 0
    
    def dfs(node, left, right, last_left=True):
        if node:
            self.ans = max(self.ans, left, right)
            # if last_left:
            #     dfs(node.right, 0, left+1, False)
            #     dfs(node.left, 1, 0, True)
            # else:
            #     dfs(node.right, 0, 1, False)
            #     dfs(node.left, right+1, 0, True)
            dfs(node.right, 0, last_left*left+1, False)
            dfs(node.left, (1-last_left)*right+1, 0, True)
            
    dfs(root, 0, 0)
    return self.ans

方法二：-1的妙用。

def longestZigZag(self, root: TreeNode) -> int:
    
    def dfs(node):
        if not node: return (-1, -1, -1)
        left, right = dfs(node.left), dfs(node.right)
        return (left[1]+1, right[0]+1, max(left[1]+1, right[0]+1, left[-1], right[-1]))
        
    return dfs(root)[-1]

1367. Linked List in Binary Tree

判断一个链表是否在二叉树的路径中。原题

方法一：递归。

def isSubPath(self, head: ListNode, root: TreeNode) -> bool:
    
    def dfs(head, root):
        if not head: return True
        if not root: return False
        return head.val==root.val and (dfs(head.next, root.left) or dfs(head.next, root.right))
    
    if not head: return True
    if not root: return False
    return dfs(head, root) or self.isSubPath(head, root.left) or self.isSubPath(head, root.right)

124. Binary Tree Maximum Path Sum

二叉树的最大路径和，可以不经过根节点。原题

Input: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

Output: 42

方法一：递归。开始有一点没想明白，对于任意节点来说，都有左右两条path, 包括根节点。

def maxPathSum(self, root: TreeNode) -> int:
    
    self.ans = float('-inf')
    
    def maxend(node):
        if not node:
            return 0
        left = maxend(node.left)
        right = maxend(node.right)
        self.ans = max(self.ans, left+right+node.val)
        return max(node.val + max(left, right), 0)
    
    maxend(root)
    return self.ans

1443. Minimum Time to Collect All Apples in a Tree

收集苹果的最小路径。原题

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,true,true,false]
Output: 8 
Explanation: The figure above represents the given tree where red vertices have an apple. One optimal path to collect all apples is shown by the green arrows.

方法一：每个苹果的路径都是节点到根的两倍距离。

def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:
    t = collections.defaultdict(int)
    for a, b in edges:
        t[b] = a
        
    used = set()
    @functools.lru_cache
    def dfs(node):
        if node == 0:
            return 0
        used.add((node, t[node]))
        return dfs(t[node]) + 1
    
    list(map(dfs, (i for i, f in enumerate(hasApple) if f)))
    return len(used) * 2

1339. Maximum Product of Splitted Binary Tree

将一个树砍成两颗树，使两个节点和乘积最大。原题

方法一：需要遍历2次，一次求出所有节点和。

def maxProduct(self, root: TreeNode) -> int:
    self.ans = total = 0
    
    def s(node):
        if not node: return 0
        left, right = s(node.left), s(node.right)
        self.ans = max(self.ans, (total-left)*left, right*(total-right))
        return left+right+node.val
    
    total = s(root)
    s(root)
    return self.ans % (10**9+7)

1315. Sum of Nodes with Even-Valued Grandparent

祖父节点为偶数的节点和。原题

def sumEvenGrandparent(self, root: TreeNode, p=1, gp=1) -> int:
    return self.sumEvenGrandparent(root.left, root.val, p) + \
        self.sumEvenGrandparent(root.right, root.val, p) + \
        root.val * (gp&1==0) if root else 0

1457. Pseudo-Palindromic Paths in a Binary Tree

伪回文路径的个数。指排列能够成为回文的路径。原题

Input: root = [2,3,1,3,1,null,1]
Output: 2 
Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the red path [2,3,3], the green path [2,1,1], and the path [2,3,1]. Among these paths only red path and green path are pseudo-palindromic paths since the red path [2,3,3] can be rearranged in [3,2,3] (palindrome) and the green path [2,1,1] can be rearranged in [1,2,1] (palindrome).

方法一：竞赛时的答案。

def pseudoPalindromicPaths (self, root: TreeNode) -> int:
    
    c = collections.defaultdict(int)
    self.count = 0
        
    def dfs(node, odd=True):
        if node:
            c[node.val] ^= 1
            if not node.left and not node.right:
                single = sum(v for v in c.values() if v==1) 
                self.count += (single==int(odd))
            dfs(node.left, not odd)
            dfs(node.right, not odd)
            c[node.val] ^= 1
    
    dfs(root)
    return self.count

方法二：因为node的值时1~9，所以这里用一个计位器count

def pseudoPalindromicPaths (self, root: TreeNode) -> int:
    
    def dfs(node, count=0):
        if not node: return 0
        count ^= 1 << (node.val-1)
        ans = dfs(node.left, count) + dfs(node.right, count)
        if node.left == node.right:
            if count & (count-1) == 0:
                ans += 1
        return ans
    
    return dfs(root)

129. Sum Root to Leaf Numbers

根到叶子节点组成的数字和。原题

Input: [1,2,3]
    1
   / \
  2   3
Output: 25
Explanation:
The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Therefore, sum = 12 + 13 = 25.

方法一：dfs 写法上迟疑了一下，还是要判断是否为根节点的，避免和累加了2次。

def sumNumbers(self, root: TreeNode) -> int:
    self.ans = 0
    
    def dfs(node, cur):
        if not node:
            return
        cur += node.val
        if not node.left and not node.right:
            self.ans += cur
        dfs(node.left, cur*10)
        dfs(node.right, cur*10)
        
    dfs(root, 0)
    return self.ans

114. Flatten Binary Tree to Linked List

将一个二叉树变成一个链表，要求在原节点上操作。原题

    1
   / \
  2   5
 / \   \
3   4   6

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

方法一：变成左子树操作直观一点，所以先将它变成左子树，然后再镜像。

def flatten(self, root: TreeNode) -> None:
    
    def dfs(node, p=[], par=None):
        p.append(node)
        if len(p) > 1:
            p[-2].left = p[-1]
            if par:
                par.right = None
        if node.left:
            dfs(node.left, p)
        if node.right:
            dfs(node.right, p, node)
        
    def sym(node):
        if node:
            node.left, node.right = node.right, node.left
            sym(node.left)
            sym(node.right)
            
    if not root:
        return 
    dfs(root)
    sym(root)

方法二：先把俩节点左右互换。

def flatten(self, root: TreeNode) -> None:
    
    def dfs(node, p=[], par=None):
        node.left, node.right = node.right, node.left
        p.append(node)
        if len(p) > 1:
            p[-2].right = p[-1]
            if par:
                par.left = None
        if node.right:
            dfs(node.right, p)
        if node.left:
            dfs(node.left, p, node
            
    if not root:
        return 
    dfs(root)

def countPairs(self, root: TreeNode, distance: int) -> int:
    paths = []
    
    def dfs(node, p):
        if node:
            p.append(node)
            if not node.left and not node.right:
                paths.append(list(p))
            dfs(node.left, p)
            dfs(node.right, p)
            p.pop()
            
    dfs(root, [])
    ans = 0
    n = len(paths)
    for i in range(n):
        for j in range(i+1, n):
            p1 = list(paths[i])
            p2 = list(paths[j])
            k = distance + 1
            while k:
                if p1[-1] == p2[-1]:
                    ans += 1
                    break
                if len(p1) >= len(p2):
                    p1.pop()
                else:
                    p2.pop()
                k -= 1
    return ans

方法二：后序遍历

def countPairs(self, root: TreeNode, distance: int) -> int:
    count = 0
    
    def dfs(node):
        nonlocal count
        if not node:
            return []
        if not node.left and not node.right:
            return [1]
        left = dfs(node.left)
        right = dfs(node.right)
        count += sum(l+r<=distance for l in left for r in right)
        return [k+1 for k in left+right if k+1<distance]
    
    dfs(root)
    return count

450. Delete Node in a BST

删除二叉搜索树的一个节点。原题

方法一：递归，好久没做二叉树有点生疏，想了半天。

def deleteNode(self, root: TreeNode, key: int) -> TreeNode:
    if not root: return
    if root.val > key:
        root.left = self.deleteNode(root.left, key)
    elif root.val < key:
        root.right = self.deleteNode(root.right, key)
    else:
        if not root.right:
            return root.left
        elif not root.left:
            return root.right
        else:
            cur = root.right
            while cur.left:
                cur = cur.left
            cur.left = root.left
            return root.right
    return root

971. Flip Binary Tree To Match Preorder Traversal

给你一个二叉树和一个前序遍历，判断二叉树否通过互换左右子树来达到前序遍历的顺序，返回这样的节点编号，没有则返回-1。原题

Input: root = [1,2], voyage = [2,1]
Output: [-1]

方法一：递归。第一次ac的方法。

def flipMatchVoyage(self, root: TreeNode, v: List[int]) -> List[int]:
    ans = []
    v = v[::-1]
    def flip(node):
        val = node.val if node else None
        if val != v[-1]:
            nonlocal ans
            ans = [-1]
            return 
        v.pop()
        if not v: return
        if node.left and node.left.val != v[-1]:
            node.left, node.right = node.right, node.left
            ans.append(node.val)
        if node.left:
            flip(node.left)
        if node.right:
            flip(node.right)
        
    flip(root)
    return ans

方法二：lee的写法。思路是一样的。

def flipMatchVoyage(self, root: TreeNode, v: List[int]) -> List[int]:
    ans = []
    v = v[::-1]
    
    def dfs(node):
        if not node: return True
        if node.val != v[-1]: return False
        v.pop()
        if node.left and node.left.val != v[-1]:
            node.left, node.right = node.right, node.left
            ans.append(node.val)
        return dfs(node.left) and dfs(node.right)
    
    return ans if dfs(root) else [-1]

951. Flip Equivalent Binary Trees

和971差不多，比较的是两棵树。原题

方法一：第一次提交时少考虑了一个case就是左右节点都相同。这种情况下可翻转也可不翻转。然后想or的关系，担心会超时。好在树的节点并没有很多。而且用时也不高beats了90%。

def flipEquiv(self, root1: TreeNode, root2: TreeNode) -> bool:
    if not root1 or not root2:
        return root1 is root2
    if root1.val != root2.val:
        return False
    left_1 = root1.left.val if root1.left else None
    left_2 = root2.left.val if root2.left else None
    ans = False
    if left_1 != left_2:
        root1.left, root1.right = root1.right, root1.left
    else:
        right_1 = root1.right.val if root1.right else None
        right_2 = root2.right.val if root2.right else None
        if left_1 == right_1 == right_2:
            ans |= (self.flipEquiv(root1.left, root2.right) and
                    self.flipEquiv(root1.right, root2.left))
    ans |= (self.flipEquiv(root1.left, root2.left) and
            self.flipEquiv(root1.right, root2.right))
    return ans

方法二：理论上来说是方法一快，但是可以忽略不计。

def flipEquiv(self, root1: TreeNode, root2: TreeNode) -> bool:
    if not root1 or not root2:
        return root1 is root2
    return (root1.val == root2.val and
           (self.flipEquiv(root1.left, root2.right) and
            self.flipEquiv(root1.right, root2.left)) |
           (self.flipEquiv(root1.left, root2.left) and
            self.flipEquiv(root1.right, root2.right)))

863. All Nodes Distance K in Binary Tree

找出树中距离目标节点为K的节点值。原题

Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2

Output: [7,4,1]

Explanation: 
The nodes that are a distance 2 from the target node (with value 5)
have values 7, 4, and 1.

方法一：这个方法想了一下，没敢往下细想。先把他变成那种无向图。然后bfs。

def distanceK(self, root: TreeNode, target: TreeNode, K: int) -> List[int]:
    g = collections.defaultdict(list)
    
    def connect(parent, child):
        if parent and child:
            g[parent.val].append(child.val)
            g[child.val].append(parent.val)
        if child.left: connect(child, child.left)  
        if child.right: connect(child, child.right)
    
    connect(None, root)
    bfs = [target.val]
    seen = set(bfs)
    for _ in range(K):
        new_level = []
        for q_val in bfs:
            for j in g[q_val]:
                if j not in seen:
                    new_level.append(j)
        bfs = new_level
        seen |= set(bfs)
    return bfs

865. Smallest Subtree with all the Deepest Nodes

带有最深节点的最小子树。也就是求最底层叶子节点的最小公共祖先。原题

方法一：用最小公共祖先的求法可以得到。

def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
    paths = []
    
    def dfs(n, p):
        if n:
            p.append(n)
            if not n.left and not n.right:
                paths.append(list(p))
            dfs(n.left, p)
            dfs(n.right, p)
            p.pop()
    
    dfs(root, [])
    max_len = max(len(p) for p in paths)
    paths = [p for p in paths if len(p)==max_len]
    return next(nodes[0] for nodes in list(zip(*paths))[::-1] if len(set(nodes))==1)

方法二：Lee215的方法。如果对于一个子树节点来说，左边深度>右边则说明我们要找的点在左侧。反之亦然。如果相等，则该节点就是我们要找的节点。返回一个tuple一层层将要找的点递归上去。

def subtreeWithAllDeepest(self, root: TreeNode) -> TreeNode:
    def deep(root):
        if not root: return 0, None
        l, r = deep(root.left), deep(root.right)
        if l[0] > r[0]: return l[0] + 1, l[1]
        elif l[0] < r[0]: return r[0] + 1, r[1]
        else: return l[0] + 1, root
    return deep(root)[1]

1373. Maximum Sum BST in Binary Tree

找到二叉树中，最大的一个二叉搜索子树所有节点的和。原题

方法一：虽然是个hard题，但是思路很清晰。一个dfs返回时记录这个子树中的最小值，最大值，总和。首次ac的方法。

def maxSumBST(self, root: TreeNode) -> int:
    self.ans = 0
    
    def helper(node):
        if not node.left and not node.right:
            self.ans = max(self.ans, node.val)
            return node.val, node.val, node.val
        if node.left:
            small_left, big_left, total_left = helper(node.left)
        else:
            small_left, big_left, total_left = float('inf'), float('-inf'), 0
        if node.right:
            small_right, big_right, total_right = helper(node.right)
        else:
            small_right, big_right, total_right = float('inf'), float('-inf'), 0
        if node.val > big_left and node.val < small_right:
            total = total_left + total_right + node.val
            small = min(small_left, small_right, node.val)
            big = max(big_left, big_right, node.val)
        else:
            small, big, total = float('-inf'), float('inf'), 0
        
        self.ans = max(self.ans, total)
        return small, big, total

方法二：方法一多了很多多余的比较。

def maxSumBST(self, root: TreeNode) -> int:
    self.ans = 0
    
    def helper(node):
        if not node:
            return float('inf'), float('-inf'), 0
        small_left, big_left, total_left = helper(node.left)
        small_right, big_right, total_right = helper(node.right)
        if big_left < node.val < small_right:
            self.ans = max(self.ans, total_left+total_right+node.val)
            return min(small_left, node.val), max(big_right, node.val), total_left+total_right+node.val
        return float('-inf'), float('inf'), 0
    
    helper(root)
    return self.ans

501. Find Mode in Binary Search Tree

找到二叉搜索树中的众数，可能有多个值。这个树左子树节点是《=当前节点。

方法一：中序遍历改的。将所有节点值按序输出就好找了。

def findMode(self, root):
    
    def inorder(node):
        if node:
            yield from inorder(node.left)
            yield node.val
            yield from inorder(node.right)
            
    prev, ans = None, []
    cnt = max_cnt = 0
    for d in inorder(root):
        if prev == d:
            cnt += 1
        else:
            cnt = 1
        if cnt > max_cnt:
            ans = [d]
        elif cnt == max_cnt:
            ans.append(d)
        max_cnt = max(max_cnt, cnt)
        prev = d
    return ans

968. Binary Tree Cameras

要对一颗二叉树进行监控，一个摄像头可以监控父节点，自身以及子节点。问最少需要多少个摄像头能监控所有节点。

方法一：这题看了题解，实际上有个贪心的解法，通过状态来表示节点是否需要监控。通过后序遍历，子节点的装填判断附近点状态。有时候看到标签上是dp，就被标签上的解法限制住了。

def minCameraCover(self, root: TreeNode) -> int:
    # 0：未被监控；1：已监控，2：摄像头
    self.ans = 0

    def dfs(node):
        if not node:
            return 1
        left = dfs(node.left)
        right = dfs(node.right)
        if left==0 or right==0:
            self.ans += 1
            return 2
        if left==1 and right==1:
            return 0
        return 1

    if dfs(root) == 0:
        self.ans += 1
    return self.ans

116. Populating Next Right Pointers in Each Node

将一个完美二叉树每层的节点相连。完美二叉树是指所有叶子节点在同一层，每个父节点都有两个子节点。

方法一：stefan.

def connect(self, root: 'Node') -> 'Node':
    head = root
    while root and root.left:
        nxt = root.left
        while root:
            root.left.next = root.right
            root.right.next = root.next and root.next.left
            root = root.next
        root = nxt
    return head

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

这题由于要求常数空间复杂度实现，提高了难度。不能使用层序直接做了。对比116题，树不是完美二叉树了。

方法一：指针，cur表示当前层游标，head表示下一层头节点，pre则是下一层的游标。逐个将pre的next和cur的左右子节点相连。

def connect(self, root: 'Node') -> 'Node':
    head = root
    while head:#当前层的头节点
        cur = head #当前层处理节点
        pre = head = None#初始化下一层头节点和前置节点
        while cur:
            if cur.left:
                if not pre:#若尚未找到下一层前置节点，则同步更新下一层头节点和前置节点
                    pre = head =cur.left
                else:#已找到下一层前置节点，则将前置节点指向当前子节点，并前移pre
                    pre.next = cur.left
                    pre = pre.next
            if cur.right:
                if not pre:
                    pre = head = cur.right
                else:
                    pre.next = cur.right
                    pre = pre.next
            cur = cur.next
    return root

834. Sum of Distances in Tree](https://leetcode.com/problems/sum-of-distances-in-tree/)

给定一个无向、连通的树。树中有 N 个标记为 0…N-1 的节点以及 N-1 条边 。返回一个表示节点 i 与其他所有节点距离之和的列表 ans。

输入: N = 6, edges = [[0,1],[0,2],[2,3],[2,4],[2,5]]
输出: [8,12,6,10,10,10]
解释: 
如下为给定的树的示意图：
  0
 / \
1   2
   /|\
  3 4 5

方法一：dfs. @lee215的方法。 属实是一道hard题，看了题解才明白。对于任意节点，可以从O(n)获取所有的距离之和。但是如果每个节点都做一遍dfs，O(n^2)明显会超时。这样思考，当根节点在无向图中移动时，比如从0到2，那么与移动方向相同的节点，所有节点距离都少了1；与之反向的节点距离都+1。那么如果知道了2节点的子树（包含2节点）一共有多少个节点，就知道了距离是如何变化的。还需要明白一件事，res[root] = res[child] + count[child]。比如以0位父节点，在0的右子树部分距离和为res[2] + count[2]，count表示2子树有多少个节点。因为对于2中所有的节点到2的距离都包含在了res[2]`中，那么需要计算到0的距离，就是所有的节点再+1。我们以0位根节点，在通过0算其他的距离和。知道了这些规律，先进行一次后序遍历更新更新res[0]和count。然后进行先序遍历更新0的各个子节点的距离和。

def sumOfDistancesInTree(self, N: int, edges: List[List[int]]) -> List[int]:
    tree = defaultdict(set)
    for u, v in edges:
        tree[u].add(v)
        tree[v].add(u)
    res = [0] * N
    count = [1] * N

    def dfs(root, pre):
        for i in tree[root]:
            if i != pre:
                dfs(i, root)
                count[root] += count[i]
                res[root] += res[i] + count[i]

    def dfs2(root, pre):
        for i in tree[root]:
            if i != pre:
                res[i] = res[root] - count[i] + N - count[i]
                dfs2(i, root)

    dfs(0, -1)
    dfs2(0, -1)
    return res

655. Print Binary Tree

打印二叉树。

Input:
     1
    / \
   2   3
    \
     4
Output:
[["", "", "", "1", "", "", ""],
 ["", "2", "", "", "", "3", ""],
 ["", "", "4", "", "", "", ""]]

方法一：iterative.

def printTree(self, root: TreeNode) -> List[List[str]]:
    level, ans, d = [root], [], 0
    while any(level):
        ans.append([str(n.val) if n else '' for n in level])
        tmp = []
        for n in level:
            if not n: tmp.extend([None, None])
            else: tmp.extend([n.left, n.right])
        level = tmp
        d += 1
        
    m = n = 2 ** d - 1
    res = []
    for layer in ans:
        tmp = [''] * n
        it = iter(layer)
        for j in range(m//2, n, m+1):
            tmp[j] = next(it)
        res.append(tmp)
        m //= 2
    
    return res

方法二：递归法也很清晰。

def printTree(self, root: TreeNode) -> List[List[str]]:
    
    def get_height(node):
        return 0 if not node else 1 + max(get_height(node.left), get_height(node.right))
    
    def update_output(i, lo, hi, node):
        if not node: return
        mid = (lo + hi) // 2
        ans[i][mid] = str(node.val)
        update_output(i+1, lo, mid-1, node.left)
        update_output(i+1, mid+1, hi, node.right)
    
    h = get_height(root)
    w = 2 ** h - 1
    ans = [[''] * w for _ in range(h)]
    lo, hi = 0, w - 1
    update_output(0, lo, hi, root)
    return ans

方法三：自己写得方法，逐层遍历，逐层更新。

def printTree(self, root: Optional[TreeNode]) -> List[List[str]]:

    def fat(row):
        new_row = [""]
        for n, e in zip(row, repeat("")):
            new_row.extend([n, e])
        return new_row

    level = [(root, 0)] # 节点, 父节点横坐标, 以root为原点
    res = [[str(root.val)]]
    while True:
        level = [(k, xk) for (n, x2) in level 
                 for (k, xk) in ((n.left, x2*2-1), (n.right, x2*2+1))
                 if k]
        # print(level)
        if not level:
            break
        for row in res:
            row[::] = fat(row)
        N = len(res[-1])
        new_row = [""] * N
        for n, px in level:
            new_row[px + N//2] = str(n.val)
        res.append(new_row)
    return res

307. Range Sum Query - Mutable

可变区间查询。

Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

方法一：标准的线段树。

class Node:
    
    def __init__(self, start, end, val=0):
        self.start = start
        self.end = end
        self.val = val
        self.left = None
        self.right = None
        
    
class NumArray:

    def __init__(self, nums: List[int]):
        
        def build_tree(lo, hi):
            if lo > hi:
                return 
            if lo == hi:
                return Node(lo, hi, nums[lo])
            mid = (lo + hi) >> 1
            root = Node(lo, hi)
            root.left = build_tree(lo, mid)
            root.right = build_tree(mid+1, hi)
            root.val = root.left.val + root.right.val
            return root
        self.root = build_tree(0, len(nums)-1)

    def update(self, i: int, val: int) -> None:
        
        def update_val(root, i, val):
            if root.start == root.end:
                root.val = val
                return
            
            mid = (root.start + root.end) >> 1
            if i <= mid:
                update_val(root.left, i, val)
            else:
                update_val(root.right, i, val)
            root.val = root.left.val + root.right.val
        
        update_val(self.root, i, val)

    def sumRange(self, i: int, j: int) -> int:
        
        def sum_range(root, i, j):
            if root.start==i and root.end==j:
                return root.val
            
            mid = (root.start + root.end) >> 1
            if j <= mid:
                return sum_range(root.left, i, j)
            elif i >= mid+1:
                return sum_range(root.right, i, j)
            else:
                return sum_range(root.left, i, mid) + sum_range(root.right, mid+1, j)
            
        return sum_range(self.root, i, j)

652. Find Duplicate Subtrees

找到重复的子树结构，相同子树返回任意节点。

Input: root = [1,2,3,4,null,2,4,null,null,4]
Output: [[2,4],[4]]

方法一：序列化+哈希。

def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:
    g = {}
    res = {}
    def dfs(node):
        if not node:
            return '#'
        else:
            left = dfs(node.left)
            right = dfs(node.right)
            cur = left + ',' + right + ',' + str(node.val)
            if cur in g:
                if cur not in res:
                    res[cur] = node
            else:
                g[cur] = node
            return cur

    dfs(root)
    return list(res.values())

方法二：使用三元组，这里的defaultdict写法很独特。

def findDuplicateSubtrees(self, root: TreeNode) -> List[TreeNode]:
    trees = defaultdict()
    trees.default_factory = trees.__len__
    c = Counter()
    res = []
    def dfs(node):
        if node:
            uid = trees[(node.val, dfs(node.left), dfs(node.right))]    
            c[uid] += 1
            if c[uid] == 2:
                res.append(node)
            return uid
    dfs(root)
    return res

1028. Recover a Tree From Preorder Traversal

通过前序遍历重建二叉树。

Input: S = "1-2--3--4-5--6--7"
Output: [1,2,5,3,4,6,7]

方法一：迭代。使用一个栈来辅助。当栈长度大于深度时，将子节点出栈。然后优先安装左子节点。

def recoverFromPreorder(self, S: str) -> TreeNode:
    stack, i, n = [], 0, len(S)
    while i < n:
        lv, val = 0, ''
        while i<n and S[i]=='-':
            lv, i = lv+1, i+1
        while i<n and S[i]!='-':
            val, i = val+S[i], i+1
        while len(stack) > lv:
            stack.pop()
        node = TreeNode(val)
        if stack and stack[-1].left is None:
            stack[-1].left = node
        elif stack:
            stack[-1].right = node
        stack.append(node)
    return stack[0]