二叉树相关

二叉搜索树

每个节点中的值必须大于存储在其左子树中的任何值
每个节点中的值必须小于存储在其右子树中的任何值
使用中序遍历能够得到一个递增的有序序列

morris遍历模版：

class Solution(object):
    def recoverTree(self, root):
        """具体任务出发，对使用到的变量进行初始化"""
        while root:
            """
            如果是中序遍历，那么先处理左子树，再处理右子树；这里以中序遍历为例
            如果是反序中序遍历，那么先处理右子树，在处理左子树
            """
            if root.left:
                # 如果当前节点左子树不为空，找到左子树的最右节点
                tmp = root.left
                while tmp.right and tmp.right != root:
                    tmp = tmp.right
                
                if not tmp.right:
                    # 如果当前节点的右子树为空，那么将当前节点的右子树链连接根节点
                    # 然后令当前节点的左子节点为当前节点，因为是中序遍历，探索到最左子树
                	tmp.right = root
                    tmp = tmp.left
                else:
                    # 如果当前节点的右子树不为空
                    """具体任务出发，对变量进行操作"""
                    # 将当前节点的右子树断开，根节点的右子树为新根节点
                    tmp.right = None
                    root = root.right
			else:
                # 如果左子树不存在
                """具体任务出发，对变量进行操作"""
                # 根节点的右子树为新根节点
                root = root.right
                
        """具体任务出发，对变量进行最终操作"""

105，从前序与中序遍序列构造二叉树，中等

核心方法：递归

对于任意一棵树而言，前序遍历的结果总是：[根结点，[左子树的前序结果]，[右子树的前序结果]]

后序遍历的结果总是：[[左子树的前序结果]，根结点，[右子树的前序结果]]

只要在中序遍历中确定了根结点的位置，那么就可以知道左右子树的节点个数，这样就可以在前序遍历的结果中对左右括号进行定位。最后通过找到的左子树（右子树）的前序结果和中序结果，然后递归调用。

可以采用哈希映射将中序遍历中各个节点值对应的序号取出来，这样能够在O(1)复杂度内查到根结点的位置。

时间复杂度：O(n)，其中 n 是树中的节点个数。
空间复杂度：O(n)，除去返回的答案需要的 O(n) 空间之外，我们还需要使用 O(n) 的空间存储哈希映射，以及 O(h)（其中 h 是树的高度）的空间表示递归时栈空间。这里 h<n，所以总空间复杂度为 O(n)。

# 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 buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        def myBuildTree(pre_left, pre_right, in_left, in_right):
            if pre_left > pre_right:
                return None
            pre_root_index = pre_left  # 前序遍历中根结点的位置，也就是第一个
            in_root_index = index[preorder[pre_root_index]]  # 中序遍历结果中的根节点

            # 把当前根节点建立出来
            root = TreeNode(preorder[pre_root_index])
            # 左子树的节点数目
            left_subtree_size = in_root_index - in_left

            # 构造左子树
            root.left = myBuildTree(pre_left+1, pre_left+left_subtree_size, in_left, in_root_index-1)
            # 构造右子树
            root.right = myBuildTree(pre_left+left_subtree_size+1, pre_right, in_root_index+1, in_right)
            return root
        
        n = len(preorder)
        index = {element: i for i, element in enumerate(inorder)}
        return myBuildTree(0 ,n-1, 0, n-1)

101，对称二叉树，简单

核心方法：递归。注意三个终止条件

时间复杂度：这里遍历了这棵树，渐进时间复杂度为 O(n)。
空间复杂度：这里的空间复杂度和递归使用的栈空间有关，这里递归层数不超过 n，故渐进空间复杂度为 O(n)。

# 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 isSymmetric(self, root: TreeNode) -> bool:
        if not root: return True
        def next(l, r):
            # 结束条件
            if not l and not r:
                # 左右节点都为空
                return True
            if not l or not r:
                # 左右节点有一个为空
                return False
            if l.val != r.val:
                # 左右节点值不想等
                return False
            return next(l.left, r.right) and next(l.right, r.left)
        return next(root.left, root.right)

核心方法：迭代，使用队列。如果当前节点满足条件，就将下面待比较的每组添加到队列中，直到队列为空

时间复杂度：O(n)
空间复杂度：O(n)

# 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 isSymmetric(self, root: TreeNode) -> bool:
        # 使用队列
        if not root: return True
        q = [(root.left, root.right)]
        
        while q:
            left, right = q.pop()
            if not left and not right:
                continue
            
            if left and right and left.val == right.val:
                q.append((left.left, right.right))
                q.append((left.right, right.left))
            else:
                return False
        return True

98，验证二叉搜索树，中等

核心方法：递归，在向下探索的过程中，不断检查左子节点，右子节点和根结点的关系是否满足条件；只要不满足条件，直接return False

时间复杂度：O(n)

空间复杂度：O(n)，树高最高为n

# 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 isValidBST(self, root: TreeNode) -> bool:
        if not root: 
            return True

        def search(node, min_v, max_v):
            if not node: 
                return True

            if node.left:
                if node.left.val >= node.val or node.left.val <= min_v:
                    return False

            if node.right:
                if node.right.val <= node.val or node.right.val >= max_v:
                    return False

            return search(node.left, min_v, node.val) and search(node.right, node.val, max_v)
        
        # 这里设置最小值和最大值，初始化最小值很小，最大值很大
        # 在向下递归的过程中，如果左子节点值小于最小值，右子节点值大于最大值，全部返回False
        return search(root, -2**32, 2**32)

根据搜索二叉树的性质，中序遍历得到的结果一定是升序的。那么通过迭代的方法，中序遍历这个树，分别记录每个节点的值，然后判断当前遍历到的值是否大于上一个值，如果不大于，则return False，全遍历完后return True。使用栈来维护每个根结点。

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

226，翻转二叉树，简单

核心方法：向下进行递归，分别取当前节点的左子节点和右子节点，然后分别将他们赋值给当前节点的右子树和左子树

时间复杂度：O(N)，每个节点遍历一遍，在常数空间内交换两颗树

空间复杂度：O(N)，使用的空间由递归栈的深度决定。最坏情况下，树形成链状，空间复杂度为O(N)

# 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 invertTree(self, root: TreeNode) -> TreeNode:
        if not root:
            return root
        
        left = self.invertTree(root.left)
        right = self.invertTree(root.right)
        root.left, root.right = right, left
        return root

543，二叉树的直径，简单

核心方法：向下递归，找到每个节点的左最大深度和右最大深度，+1得到当前节点下的最多节点路径。比较每个节点的最多节点路径并维护。遍历完成后，最长直径等于最多节点路径上的最长直径，也就是节点数-1

时间复杂度：O(N)

空间复杂度：O(N)

# 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 diameterOfBinaryTree(self, root: TreeNode) -> int:
        # 维护一个变量记录每次递归完成后的路径经的所有节点数
        self.ans = 1
        def depth(node):
            if not node: return 0
            # 先找到每个根节点的左子树节点
            L = depth(node.left)
            # 再找到每个根节点的右子树节点
            R = depth(node.right)
            # 更新最多的节点数，加1表示计算了当前节点
            self.ans = max(self.ans, L+R+1)
            # 返回（左或右）最大深度，加1表示计算了当前节点
            return max(L, R) + 1

        depth(root)
        # 最长直径等于路径上最多节点数-1
        return self.ans - 1

110，平衡二叉树，简单

核心方法：从根节点开始，向下递归，检查左右子树是否是平衡的。递归返回的是从当前节点开始的最大深度（不忘记算上当前节点，要+1）。在递归的过程中，只要遇到某节点的左右子树有一个等于-1，即深度差大于1，就一直向上返回-1，在最顶端判断为False；否则判断为True

时间复杂度：O(N)

空间复杂度：O(N)

# 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 isBalanced(self, root: TreeNode) -> bool:
        def recur(root):
            if not root:
                return 0
            
            left = recur(root.left)
            if left == -1: 
                return -1
            
            right = recur(root.right)
            if right == -1: 
                return -1
            return max(left, right) + 1 if abs(left- right) < 2 else -1
        
        return recur(root) != -1

剑指offer32，从上到下打印二叉树，中等

核心方法：二叉树的层级遍历，使用队列。将每个节点放进队列。从队列中取出一个节点，将其值保存，将其左右节点加入队列。

时间复杂度：O(N)

空间复杂度：O(N)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[int]:
        if not root: return []
        queue = [root]
        res = list()
        while queue:
            node = queue.pop(0)
            res.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        return res

297，二叉树的序列化与反序列化，困难

核心方法：

序列化的方法使用层级遍历的方式，要注意的是如果遍历的节点为空，那么需要向结果列表中添加 ‘None’。返回时需要注意将结果列表变为字符串
反序列化的方法，首先将第一个值进行节点化，将当前节点放入双端队列。只要队列不为空，就弹出一个节点，按顺序取序列化列表中两个值，只要不为空，就分别将他们设置为节点然后接在当前节点下，成为左子节点和右子节点。最后返回root节点就行。
时间复杂度：O(N)
空间复杂度：O(N)

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Codec:

    def serialize(self, root):
        """Encodes a tree to a single string.
        
        :type root: TreeNode
        :rtype: str
        """
        if not root: return ''
        queue = [root]
        res = list()
        while queue:
            node = queue.pop(0)
            if node:
                res.append(str(node.val))
                queue.append(node.left) 
                queue.append(node.right)
            else:
                res.append('None')
        return '[' + ','.join(res) + ']'
        

    def deserialize(self, data):
        """Decodes your encoded data to tree.
        
        :type data: str
        :rtype: TreeNode
        """
        if not data: return []
        datalist = data[1:-1].split(',')
        root = TreeNode(int(datalist[0]))
        queue = collections.deque([root])
        i = 1
        while queue:
            node = queue.popleft()
            if datalist[i] != 'None':
                node.left = TreeNode(int(datalist[i]))
                queue.append(node.left)
            i += 1
            
            if datalist[i] != 'None':
                node.right = TreeNode(int(datalist[i]))
                queue.append(node.right)
            i += 1
        return root

        

# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.deserialize(codec.serialize(root))

236，二叉树的最近公共祖先，简单

核心方法：向下递归，如果当前节点为空，或者等于p或q中的一个，说明到头了；或是找到了p或q，此时返回当前节点。查看返回的左右节点，如果一个为空，那么就返回另一个。

也就是说，当向下递归找到p和q时，向上传递的就是p和q，或者为空。当遇到p和q的最近公共祖先时，返回的就是当前节点，也就是最近公共祖先，对应于函数最下面的 return root

时间复杂度：O(N)
空间复杂度：O(N)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if not root or root == p or root == q:
            return root
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)
        if not left: return right
        if not right: return left
        return root

671，二叉树中第二小的节点，简单

核心方法：递归+排序

使用哈希集合记录树中所有的唯一值，即使多个节点有相同值，值的唯一性会在集合中保证。递归完成后，将集合结果转化为列表，然后对其排序

时间复杂度：递归为O(n)，排序复杂度为O(nlogn)，最大为O(nlogn)
空间复杂度：在于哈希集合，最坏情况下为O(n)

# 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 findSecondMinimumValue(self, root: TreeNode) -> int:
        def dfs(node):
            if not node:
                return 
            vals.add(node.val)
            dfs(node.left)
            dfs(node.right)
        
        if not root: return -1
        vals = set()
        dfs(root)
        if len(vals) < 2:
            return -1
        res = list(vals)
        res.sort()
        return res[1]

只使用递归，如果当前节点不等于（根据这种树的性质，那就一定是大于）根节点的值，则比较（当前节点，递归左节点，递归右节点），找到最小值；反之则递归左右子节点，找最小值（不等于根节点的值）

时间复杂度： O(n)

空间复杂度： O(n)

class Solution:
    def findSecondMinimumValue(self, root: TreeNode) -> int:
        judge = root.val
        def find(root):
            if not root:
                return 1000000000000
            if root.val == judge:
                return min(find(root.left),find(root.right))
            return min(root.val,find(root.left),find(root.right))
        second = find(root)
        return second if second !=1000000000000 else -1

440，字典序的第k小的数，困难

字典序表示的是，以数字i开头的数一定要排在以数字i+1开头的数的前面。

对n=13，排序的结果就是1，10，11，12，13，2，3，4，5，6，7，8，9

在计算第k个数时，假设知道数字i开头的数有count个，那么如果这个 count > k 时，说明就不需要再去看以数字 i+1 开头的数有多少个了，直接在 count 个数中找就行；如果 count < k，那就需要去以 i+1开头的数中寻找，所以我们首先需要确定

以数字i开头的数有多少个？

首先我们需要确定一个区间，这个区间内的所有数都是以i开头的。首先我们可以确定区间的起始点就是i，区间的终点是i+1，并且只要i <= n，我们就能找到以数字i为起点的，不超过n的个数。每次累加以 i 为开头的数完成后，需要将a*10，b*10，这样做的原因是能够取到以 i 开头的，数长度从小到大的所有数。代码如下：

def getCount(prefix, n):
    count = 0
    a = prefix
    b = prefix + 1
    while a <= n:
        count += min(n+1, b) - a
        a *= 10
        b *= 10
        return count

模拟：

以 i 开头的累加数是通过区间终点减去区间起点完成的。但是以 i 开头的数字不能超过最大数字 n，所以要在最大数字 n+1 和区间终点 b 之间取一个最小。
数字i是逐步确定的，并且从1开始。用例子 n = 13, k = 2 进行一次简单的模拟。现在要计算以 1 为开头的数字个数，那么令a=1，b=a+1=2，a<n 且 b < n+1, 那么累加后的 count = 1，也就是在数长度为 1 时，以 1 开头的数只有 1，也就是1个；都乘以10后，a=10，b = 20，a < n 但是 b > n+1，那么区间长度就是 n+1-a = 4，就是以1开头的数，且长度为2的数有10，11，12，13；累加后的 count 等于 5，也就是以1开头的数为1，10，11，12，13，对应着正确的排序。

在确定以i开头的数字个数后，下一步需要确定排序后的第k个数，那么

如何找到第k个数的位置？

假设所有排序的起点是p，我们指定p从1开始（因为要求的也是第k小的数，也就是排序结果中的第k个数）。那么我们判断位置p是否等于位置k。

当然位置p是一步步往向后取的，如果当前位置与以i开头的数字个数的和大于k，说明新产生的，以i开头的数字个数与上一步（i-1开头的数字个数）已经排序的序列结果拼接后，已经包含了位置k，那么这时需要将数字i*10，也就是进入到新增的序列中查找位置k，同时位置p向后移动一位，因为新数字i字典序向后移动一位了

if p + cnt > k:
    prefix *= 10
    p += 1

模拟：承接上一个模拟结果，当p = 1，cnt = 5时，p + cnt > k，那么将p+=1，此时等于2；prefix * 10 = 10，将 prefix=10，n=13 再拿到 getCount 中进行计算。由上文可知，这个条件下getCount的计算结果是4，也就是序列10，11，12，13；此时的循环中p = k了，那么我们返回的prefix就是第k个数。

同理，如果当前位置与以i开头的数字个数的和小于等于k，说明新产生的，以i开头的数字个数与上一步（i-1开头的数字个数）已经排序的序列结果拼接后，还没有包含位置k，那么这时需要将数字i+=1，也就是获取下一个数开头的数字个数，同时位置p向后走过cnt个位置，因为这个cnt个位置不包含位置k，可以跳过。

else:
    prefix += 1
    p += cnt

总的代码表示为：

class Solution:
    def findKthNumber(self, n: int, k: int) -> int:
        def getCount(prefix, n):
            count = 0
            a = prefix
            b = prefix + 1
            while a <= n:
                count += min(n+1, b) - a
                a *= 10
                b *= 10
            return count 
        
        p = 1
        prefix = 1
        while p < k:
            cnt = getCount(prefix, n)
            if p + cnt > k:
                prefix *= 10
                p += 1
            else:
                prefix += 1
                p += cnt
        return prefix

时间复杂度：$O((log_{10}n)^2)$，两层循环嵌套，但是每10个遍历一次

空间复杂度：O(1)

814，二叉树剪枝，中等

核心方法：判断以node为根的子树中是否包含1。不包含1的情况对应，node本身不为1，且node的左右子节点为根时的左右子树都不包含1.

如果node的左右子节点为根的子树不包含1，那么我们就需要把对应的指针置为空。

在递归结束后，如果整个二叉树都不包含1，那么返回None，否则返回整棵树的根节点

时间复杂度：O(n)，n为节点个数

空间复杂度：O(h)，h 是树的高度，为我们在递归时使用的栈空间大小

class Solution(object):
    def pruneTree(self, root):
        def containsOne(node):
            if not node: return False
            a1 = containsOne(node.left)
            a2 = containsOne(node.right)
            if not a1: node.left = None
            if not a2: node.right = None
            return node.val == 1 or a1 or a2

        return root if containsOne(root) else None

99，恢复二叉搜索树，中等

核心方法：将整个树通过中序遍历，依次保存树中的每个节点。保存节点的序列中应该是递增的，若只有两个节点被交换了。那么直接找到第一个递减位置的前一个位置（即被交换的第一个位置）。找到第二个递减位置（即被交换的第二个位置），互换即可。

时间复杂度：O(n)

空间复杂度：O(n)

class Solution:
    def recoverTree(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
 		# 遍历整棵树
        out = list()
        def dfs(root):
            if not root:
                return 
            dfs(root.left)
            out.append(root)
            dfs(root.right)
        dfs(root)
        # 遍历找到需要替换位置的两个节点
        x, y = None, None
        pre = out[0]
        for i in range(1, len(out)):
            if pre.val >= out[i].val:
                # 记录第二个要替换的位置
                y = out[i]
                if not x:
                    # 记录第一个要替换的位置
                    x = pre
            pre = out[i]
        # 对节点内的两个值进行替换
        if x and y:
            x.val, y.val = y.val, x.val

核心方法：Morris遍历，使得空间复杂度为O(1)

对于某个节点，如果其左子树的右子树已经完成遍历了，那么对于递归来说，操作系统自动出栈，然后就会访问当前节点。假如我们直接将当前节点的左子树的右子树最后一个节点直接指向当前节点，那么就省去了额外的栈空间。利用叶子节点的右子树这个特点，将其重新赋予指向关系，就是莫里斯遍历的核心。

==所谓新加的指向关系，就是找到根节点左子树的最右子树，然后将最右子树的right指向根节点。==

注意：新加的关系有可能使得原来的链式存储变成图，在遍历到某一根节点时，就可以将新加的，与其相连的节点的右子树重新置为空。

比较好记的思路：从中序遍历上看

拿到一个新的根节点，首先判断其左子节点是否存在，这符合中序遍历的要求
循环检查当前节点是否存在右子节点，且右子节点不等于根节点，也就是找到根节点左子树的最右子树
上一步结束的可能是因为右子树等于了根节点，所以还需要判断一次（当前节点的右子树为空），将当前节点的右子树节在根节点处，同时根节点继续向左子树移动，这也符合中序遍历的结果
如果当前节点的右子树不为空，那么就需要计算前一个节点是否大于当前根节点，如果大于，说明找到了异常值。然后更新前一个节点为当前节点，更新根节点为当前根节点的右子树（目的是为了重新走一遍之前走过的路，将新加的最右子节点与根节点的连接断开）。

时间复杂度：O(n)

空间复杂度：O()

class Solution(object):
    def recoverTree(self, root):
        x = None  # 记录找到的第一个要替换的值
        y = None  # 记录找到的第二个要替换的值
        pre = None  # 表示前一个节点，也就是中序遍历中上一个节点
        tmp = None  # 表示当前节点
        while root:
            if root.left:
                # 如果左子树存在，将左子树赋值给tmp
                tmp = root.left
                while tmp.right and tmp.right != root:
                    # 如果当前节点的右子树存在，且这个右子树不等于根节点
                    tmp = tmp.right
                if not tmp.right:
                    # 如果当前节点的右子树为空，那么将当前节点的右子树链连接根节点
                    # 然后令当前节点的左子节点为当前节点，因为是中序遍历，探索到最左子树
                	tmp.right = root
                    tmp = tmp.left
                else:
                    # 如果当前节点的右子树不为空
                    # 需要判断前一个节点和根节点的大小关系
                    if pre and pre.val>root.val:
                        y = root
                        if not x:
                            x = pre
                    # 将根节点赋值给前一个节点，将当前节点的右子树断开，根节点的右子树为新根节点
                    pre = root
                    tmp.right = None
                    root = root.right
			else:
                # 如果左子树不存在
                # 需要判断前一个节点和根节点的大小关系
                if pre and pre.val > root.val:
                    y = root
                    if not x:
                        x = pre
                # 将根节点赋值给前一个节点，根节点的右子树为新根节点
                pre = root
                root = root.right
        if x and y:
            x.val, y.val = y.val, x.val

96，不同的二叉搜索树，中等

核心方法：遍历序列[1..n]，每个i作为根，[1, ..., i-1]作为左子树，[i+1, ..., n]作为右子树。包含重叠子问题，所以可以使用动态规划。

定义两个函数：

$G(n)$: 长度为 n 的序列能构成的不同二叉搜索树的个数。
$F(i, n)$: 以 i 为根、序列长度为 n 的不同二叉搜索树个数 (1≤i≤n)。

$G(n) = \sum_{i=1}^nF(i,n)$

当序列长度为1（只有根）或0（空树）时，只要一种情况，即$G(0)=1$, $G(1)=1$

给定序列 1⋯n，我们选择数字 i 作为根，则根为 i 的所有二叉搜索树的集合是左子树集合和右子树集合的笛卡尔积

那么$F(i, n) = G(i-1)G(n-i)$，两个公式进行结合后，得到状态转移方程

$G(n) = \sum_{i=1}^nG(i-1)G(n-i)$

时间复杂度：O(n^2)

空间复杂度：O(n)

class Solution:
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        G = [0]*(n+1)
        G[0], G[1] = 1, 1

        for i in range(2, n+1):
            for j in range(1, i+1):
                G[i] += G[j-1] * G[i-j]

        return G[n]

$G(n)$函数的值在数学上被称为卡塔兰数 $C_n$。公式表示为：

$C_0 = 1, C_{n+1} = \frac {2(2n+1)}{n+2} C_n$

时间复杂度 : O(n) 空间复杂度 : O(1)

class Solution(object):
    def numTrees(self, n):
        """
        :type n: int
        :rtype: int
        """
        C = 1
        for i in range(0, n):
            C = C * 2*(2*i+1)/(i+2)
        return int(C)

437，路径总和3，中等

记录每条路径上的前缀和。前缀和。就是到达当前元素的路径上，之前所有元素的和。只需计算每一步中，sum在数组sumlist中出现的次数，然后与每一轮递归的结果相加即可。count计算本轮sum在数组sumlist中出现的次数

时间复杂度：O(n)，每个节点遍历一遍

空间复杂度：O(n)，递归栈空间需要的大小

# 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 pathSum(self, root: TreeNode, targetSum: int) -> int:
        def dfs(root, sumlist):
            if not root:
                return 0
            sumlist = [num + root.val for num in sumlist]
            sumlist.append(root.val)

            count = 0
            for num in sumlist:
                if num == targetSum:
                    count += 1
            
            return count + dfs(root.left, sumlist) + dfs(root.right, sumlist)
        return dfs(root, [])

114，二叉树展开为链表，中等

核心方法：前序遍历二叉树，将每个节点保存到列表中，然后遍历列表，将每个节点的左子树设定为None，将右子树设定为列表中的下一个节点

时间复杂度：O(n)，其中 n 是二叉树的节点数。前序遍历的时间复杂度是 O(n)，前序遍历之后，需要对每个节点更新左右子节点的信息，时间复杂度也是 O(n)。

空间复杂度：O(n)，空间复杂度取决于栈（递归调用栈或者迭代中显性使用的栈）和存储前序遍历结果的列表的大小

# 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 flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        preorderList = list()

        def preorderTraversal(root: TreeNode):
            if root:
                preorderList.append(root)
                preorderTraversal(root.left)
                preorderTraversal(root.right)
        
        preorderTraversal(root)
        size = len(preorderList)
        for i in range(1, size):
            prev, curr = preorderList[i - 1], preorderList[i]
            prev.left = None
            prev.right = curr

使用迭代的方法：

# 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 flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        preorder = list()
        stack = list()
        node = root
        while node or stack:
            while node:
            	preorder.append(node)
                stack.append(node)
                node = node.left
            node = stack.pop()
            node = node.right
            
        size = len(preorderList)
        for i in range(1, size):
            prev, curr = preorderList[i - 1], preorderList[i]
            prev.left = None
            prev.right = curr

核心方法：前序遍历和展开同步进行，需要栈

使用前面的方法，在节点展开后会破坏二叉树的结构而丢失子节点的信息，主要是由于对左子树遍历时，没有存储右子树的信息，而是在左子树遍历完毕后才会获得右子树信息。需要使用栈，在遍历左子树之前就存储左右子节点的信息，然后就可以将前序遍历和展开同时进行。

这种做法只适用于迭代方法。每次从栈内弹出一个节点作为当前访问的节点，获得该节点的子节点，如果子节点不为空，则依次将右子节点和左子节点压入栈内（注意入栈顺序）。

时间复杂度：O(n)

空间复杂度：O(n)

# 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 flatten(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        if not root:
            return 
        # 开始遍历前，需要将prev设置为None
        stack = [root]
        prev = None
        while stack:
            curr = stack.pop()  # 每次从栈中弹出一个节点
            if prev:
                # 如果prev不为空，重新开始拼接
                prev.left = None
                prev.right = curr
            left, right = curr.left, curr.right
            # 这里注意左右子树的入栈顺序
            # 因为前序，需要保证下一次弹出的是左子树，所以左子树要比右子树后入栈
            if right:
                stack.append(right)
            if left:
                stack.append(left)
            # 更新前一个节点
            prev = curr

核心方法：寻找前驱节点

如果一个节点的左子节点为空，则该节点不需要进行展开；如果左子节点不为空，那么左子树的最后一个节点（也就是左子树的最后一个节点）被访问之后，节点的右子节点被访问；此时左子树最右边的节点就是要找的前驱节点。
对于当前节点，如果左子树节点不为空，则在其左子树中找到最右边的节点，最为前驱节点，将当前节点的右子节点赋给前驱节点的右子节点，然后将当前节点的左子节点赋给当前节点的右子节点，并将当前节点的左子节点设为空。对当前节点处理结束后，继续处理链表中的下一个节点，直到所有节点处理完。

时间复杂度：O(n)

空间复杂度：O(1)

class Solution:
    def flatten(self, root: TreeNode) -> None:
        curr = root
        while curr:
            if curr.left:
                # last 表示前驱节点，nxt当前节点的左子节点
                last = nxt = curr.left
                while last.right:
                    # 一直找到左子树的最右节点，即前驱节点
                    last = last.right
                # 当前节点的右子树赋值给前驱节点的右子树
                last.right = curr.right
                # 当前节点左子树置为空，右子树为左子树
                curr.left = None
                curr.right = nxt
            # curr移向链表的最后一个
            curr = curr.right

538，把二叉搜索树转化为累加树，中等

核心方法：中序遍历

首先使用递归中序遍历，将每个节点的值全部取出来
然后再使用一次迭代的中序遍历，找到每个节点应该赋予的值，也就是上一次遍历结果的数组，索引开始的位置向后求和，每次处理完一个节点后，索引+1

时间复杂度：O(n)

空间复杂度：O(n)

# 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 convertBST(self, root: TreeNode) -> TreeNode:
        # 首先使用中序遍历一遍
        def inorder(node):
            if not node:
                return 
            inorder(node.left)
            res.append(node.val)
            inorder(node.right)
        # 获取中序遍历的结果
        res = list()
        inorder(root)
        # 使用迭代法进行中序遍历，然后每个点进行赋值
        stack = list()
        i = 0
        node = root
        while node or stack:
            while node:
                stack.append(node)
                node = node.left
            node = stack.pop()
            node.val = sum(res[i:])
            i += 1
            node = node.right
        return root

核心方法：反序中序遍历

本题中要求将每个节点的值修改为原来的节点值加上所有大于它的节点值之和。这样只需要反序中序遍历该二叉搜索树，记录过程中的节点值之和，并不断更新当前遍历到的节点的节点值，即可得到题目要求的累加树。

时间复杂度：O(n)

空间复杂度：O(n)

# 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 convertBST(self, root: TreeNode) -> TreeNode:
        def reverseOrder(node):
            nonlocal total
            if node:
                reverseOrder(node.right)
                total += node.val
                node.val = total
                reverseOrder(node.left)
        
        total = 0
        reverseOrder(root)
        return root

Morris 遍历的核心思想是利用树的大量空闲指针，实现空间开销的极限缩减。其反序中序遍历规则总结如下：

如果当前节点的右子节点为空，处理当前节点，并遍历当前节点的左子节点；
如果当前节点的右子节点不为空，找到当前节点右子树的最左节点（该节点为当前节点中序遍历的前驱节点）；
- 如果最左节点的左指针为空，将最左节点的左指针指向当前节点，遍历当前节点的右子节点；
- 如果最左节点的左指针不为空，将最左节点的左指针重新置为空（恢复树的原状），处理当前节点，并将当前节点置为其左节点（相当于当前节点的右子节点处理完毕，要继续处理当前节点的左子节点）；

重复步骤 1 和步骤 2，直到遍历结束。

时间复杂度：O(n)，其中 n 是二叉搜索树的节点数。没有左子树的节点只被访问一次，有左子树的节点被访问两次。

空间复杂度：O(1)。只操作已经存在的指针（树的空闲指针），因此只需要常数的额外空间。

class Solution:
    def convertBST(self, root: TreeNode) -> TreeNode:
        def getSuccessor(node: TreeNode) -> TreeNode:
            succ = node.right
            while succ.left and succ.left != node:
                succ = succ.left
            return succ
        
        total = 0
        node = root

        while node:
            if not node.right:
                total += node.val
                node.val = total
                node = node.left
            else:
                succ = getSuccessor(node)
                if not succ.left:
                    succ.left = node
                    node = node.right
                else:
                    succ.left = None
                    total += node.val
                    node.val = total
                    node = node.left
        return root

617，合并二叉树，简单

核心方法：递归

# 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 mergeTrees(self, root1: TreeNode, root2: TreeNode) -> TreeNode:
        # 使用迭代式的方法，同时遍历两棵树，然后对应位置相加
        if not root1:
            return root2
        if not root2:
            return root1
        
        merged = TreeNode(root1.val + root2.val)
        merged.left = self.mergeTrees(root1.left, root2.left)
        merged.right = self.mergeTrees(root1.right, root2.right)
        return merged

450，删除二叉搜索树的节点，中等

核心方法：二叉搜索树的性质

判断当前节点的值与要求值的大小关系，如果当前节点值小，那么就从当前节点的左子树中找；如果当前节点值大，那么就从当前节点的右子树中找；
如果当前节点和要求值相同，那么需要检查左右子树是否为空，这样做的目的是，如果当前节点的值被删掉，那么为了维护二叉搜索树的性质，需要从右子树中找到一个最小值添加到当前节点的位置；然后右子树中必须再删掉这个最小值

时间复杂度：O(logN)，N为节点总数

空间复杂度：O(h)，h为树的高度

# 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 deleteNode(self, root: TreeNode, key: int) -> TreeNode:
        def getMin(node):
            while node.left:
                node = node.left
            return node
        
        if not root:
            return 
        if root.val == key:
            if not root.left: return root.right
            if not root.right: return root.left
            # 获取右子树中的最小节点，最小节点一定是在最左边
            minNode = getMin(root.right)
            root.val = minNode.val
            root.right = self.deleteNode(root.right, minNode.val)
        elif root.val > key:
            root.left = self.deleteNode(root.left, key)
        elif root.val < key:
            root.right = self.deleteNode(root.right, key)
        return root

109，有序链表转化二叉搜索树，中等

核心方法：分治

为了构造出平衡的二叉搜索树，也就需要尽可能将链表的中位数（链表长度为奇数，中位数就是中间节点；链表长度为偶数，中位数就是中间两个节点）作为二叉树的根；小于中位数的元素组成左子树，大于中位数的元素组成右子树；
使用分治的思想，递归对左右子树进行构造，找出对应的中位数作为根节点。使用「左闭右开」的方法，即 left 包含在链表中而 right 不包含在链表中。可以直接用 (left, mid) 以及 (mid.next, right) 来表示左右子树对应的列表了。并且，初始的列表也可以用 (head, null) 方便地进行表示，其中 null 表示空节点。

时间复杂度：O(nlogn)，n是链表长度。设长度为 n 的链表构造二叉搜索树的时间为 T(n)，递推式为：T(n)=2⋅T(n/2)+O(n) 其中 O(n) 为链表遍历的时间复杂度，根据主定理，T(n) = O(nlogn)。

空间复杂度：O(logn)，这里只计算除了返回答案之外的空间。平衡二叉树的高度为 O(logn)，即为递归过程中栈的最大深度，也就是需要的空间。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# 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 sortedListToBST(self, head: ListNode) -> TreeNode:
        def findMedium(left, right):
            # 找到给定链表的中位数
            fast = slow = left
            while fast != right and fast.next != right:
                fast = fast.next.next
                slow = slow.next
            return slow

        def buildTree(left, right):
            if left == right:
                return None
            # 高度相等，找到链表中点，作为二叉树的根
            mid = findMedium(left, right)
            # 构造树
            root = TreeNode(mid.val)
            root.left = buildTree(left, mid)
            root.right = buildTree(mid.next, right)
            return root
        return buildTree(head, None)

核心方法：分治 + 中序遍历优化（利用）

上一种解法的时间复杂度的问题在于寻找中位数节点。但是构造出的二叉搜索树的中序遍历结果本身就是链表的结果，因为可以将分治与中序遍历结合起来。

首先计算出链表的长度，然后使用双闭区间，指定left和right的编号，那么中位数节点对应的编号为 mid = (left + right + 1) // 2
左右子树对应的编号范围分别是 [left, mid-1] [mid+1, right]，如果 left > right，那么遍历到的位置对应着一个空节点，否则对应着二叉搜索树中的一个节点。

时间复杂度：O(n)。其中 n 是链表的长度。设长度为 n 的链表构造二叉搜索树的时间为 T(n)，递推式为 T(n)=2⋅T(n/2)+O(1)，根据主定理，T(n)=O(n)。

空间复杂度：O(logn)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# 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 sortedListToBST(self, head: ListNode) -> TreeNode:
        def getLength(head):
            # 获得链表长度
            length = 0
            while head:
                length += 1
                head = head.next
            return length
        
        def buildTree(left, right):
            if left > right:
                return None
            mid = (left + right + 1) // 2
            root = TreeNode()
            # 中序遍历
            root.left = buildTree(left, mid-1)
            nonlocal head
            root.val = head.val
            head = head.next
            root.right = buildTree(mid+1, right)
            return root

        length = getLength(head)
        return buildTree(0, length-1)

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

二叉树.md

二叉树.md

Files

二叉树.md

Latest commit

History

二叉树.md

File metadata and controls