LeetCode Cookbook 树（3）

CSDN话题挑战赛第2期
参赛话题：算法题解

LeetCode Cookbook 树（3）

   本节内容主要与 二叉搜索树 相关。

96. 不同的二叉搜索树（model-VI 二叉搜索树）

题目链接：96. 不同的二叉搜索树
题目大意：给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

例如：

输入：n = 3
输出：5

• 解题思路：动态规划 左子树个数 与 右子树个数 的乘积。
• 时间复杂度：$O(N^2)$ N为二叉搜索树的结点数
• 空间复杂度：$O(N)$

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0]*(n+1)
        dp[0],dp[1] = 1,1
        for i in range(2,n+1):
            for j in range(1,i+1):
                # 左子树结点个数为 j-1 右子树结点个数i-j
                dp[i] += dp[j-1]*dp[i-j]
            #     print(dp)
            # print('-------------------')
        return dp[n]

95. 不同的二叉搜索树 II（model-VI 二叉搜索树）

题目链接：95. 不同的二叉搜索树 II
题目大意：给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 n 互不相同的不同 二叉搜索树 。可以按 任意顺序 返回答案。

例如：

输入：n = 3
输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

解题思路： DFS 来做这道题， 需要注意每一次都需要建树的操作 for 循环中 套 双 for 循环。

• 时间复杂度：$O(\frac{4^n}{n^{1/2}}))$ 时间复杂度与空间复杂度 和 卡特兰数 相关
• 空间复杂度：$O(\frac{4^n}{n^{1/2}}))$

# 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 generateTrees(self, n: int) -> List[Optional[TreeNode]]:

        def generate(start: int,end: int) -> List[List[int]]:
            if start > end: return [None,]
            ans = list()
            for i in range(start,end+1):
                # 左子树合集 右子树合集
                leftTree = generate(start,i-1)
                rightTree = generate(i+1,end)

                # 拼树 左子树 右子树 和 一个根结点
                for L in leftTree:
                    for R in rightTree:
                        curTree = TreeNode(i)
                        curTree.left = L
                        curTree.right = R 
                        ans.append(curTree)
            return ans
        return generate(1,n) if n else []

99. 恢复二叉搜索树（model-VI 二叉搜索树）

题目链接：99. 恢复二叉搜索树
题目大意：给你二叉搜索树的根节点 root ，该树中的 恰好 两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。

例如：

输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。

输入：root = [3,1,4,null,null,2]
输出：[2,1,4,null,null,3]
解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。

• 解题思路： 中序遍历 结合二叉搜索树的特性 即： 左子树 根节点 右子树 找不符合要求的两个结点，而后 交换两个结点的值即可。
• 时间复杂度：$O(N)$ 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 __init__(self):
        self.first,self.second = None,None
        self.preNode = TreeNode(float('-inf'))

    def inOrder(self,root: Optional[TreeNode]) -> None:
        if root is None: return 
        self.inOrder(root.left)
        if self.first == None and self.preNode.val >= root.val:
            self.first = self.preNode
        if self.first and self.preNode.val >= root.val:
            self.second = root
        self.preNode = root
        self.inOrder(root.right)

    def recoverTree(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        self.inOrder(root)
        self.first.val,self.second.val = self.second.val,self.first.val

114. 二叉树展开为链表（model-VI 二叉搜索树）

题目链接：114. 二叉树展开为链表
题目大意：给你二叉树的根结点 root ，请你将它展开为一个单链表：

• 展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
• 展开后的单链表应该与二叉树 先序遍历 顺序相同

例如：

输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

• 解题思路： 按题意一步一步做 即可。
• 时间复杂度：$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 flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        # 根左右 前序遍历
        res = list()
        
        def preOrder(root: Optional[TreeNode]) -> None:
            if root is None: return 
            res.append(root)
            preOrder(root.left)
            preOrder(root.right)
        
        preOrder(root)
        n = len(res)
        for i in range(n-1):
            prev,curr = res[i],res[i+1]
            prev.left = None
            prev.right = curr

173. 二叉搜索树迭代器（model-VI 二叉搜索树）

题目链接：173. 二叉搜索树迭代器
题目大意：实现一个二叉搜索树迭代器类BSTIterator ，表示一个按中序遍历二叉搜索树（BST）的迭代器：

• BSTIterator(TreeNode root) 初始化 BSTIterator 类的一个对象。BST 的根节点 root 会作为构造函数的一部分给出。指针应初始化为一个不存在于 BST 中的数字，且该数字小于 BST 中的任何元素。
• boolean hasNext() 如果向指针右侧遍历存在数字，则返回 true ；否则返回 false 。
• int next()将指针向右移动，然后返回指针处的数字。
  注意，指针初始化为一个不存在于 BST 中的数字，所以对 next() 的首次调用将返回 BST 中的最小元素。
  你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 的中序遍历中至少存在一个下一个数字。

例如：

输入
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
输出
[null, 3, 7, true, 9, true, 15, true, 20, false]

解释
BSTIterator bSTIterator = new BSTIterator([7, 3, 15, null, null, 9, 20]);
bSTIterator.next();    // 返回 3
bSTIterator.next();    // 返回 7
bSTIterator.hasNext(); // 返回 True
bSTIterator.next();    // 返回 9
bSTIterator.hasNext(); // 返回 True
bSTIterator.next();    // 返回 15
bSTIterator.hasNext(); // 返回 True
bSTIterator.next();    // 返回 20
bSTIterator.hasNext(); // 返回 False

• 解题思路： 借助 双头队列 建树。
• 时间复杂度：构造函数 $O(N)$ N为二叉搜索树的结点数 ；next（）方法为$O(1)$
• 空间复杂度：$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 BSTIterator:

    def __init__(self, root: Optional[TreeNode]):
        self.q = collections.deque()
        self.inOrder(root)

    def inOrder(self,root) -> None:
        if root is None: return
        self.inOrder(root.left)
        self.q.append(root.val)
        self.inOrder(root.right)

    def next(self) -> int:
        return self.q.popleft()

    def hasNext(self) -> bool:
        return len(self.q)>0

# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()

1382. 将二叉搜索树变平衡（model-VI 扩展）

题目链接：1382. 将二叉搜索树变平衡
题目大意：给你一棵二叉搜索树，请你返回一棵 平衡后 的二叉搜索树，新生成的树应该与原来的树有着相同的节点值。如果有多种构造方法，请你返回任意一种。
如果一棵二叉搜索树中，每个节点的两棵子树高度差不超过 1 ，我们就称这棵二叉搜索树是 平衡的 。

例如：

输入：root = [1,null,2,null,3,null,4,null,null]
输出：[2,1,3,null,null,null,4]
解释：这不是唯一的正确答案，[3,1,4,null,2,null,null] 也是一个可行的构造方案。

• 解题思路： 中序遍历二叉树 二分法建树。
• 时间复杂度：$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 balanceBST(self, root: TreeNode) -> TreeNode:
        def inOrder(o: TreeNode):
            if o.left: inOrder(o.left)
            inOrderSeq.append(o.val)
            if o.right: inOrder(o.right)
        
        def build(L,R) -> TreeNode:
            if L>R: return None
            mid = L+(R-L)//2
            o = TreeNode(inOrderSeq[mid])
            o.left = build(L,mid-1)
            o.right = build(mid+1,R)
            return o 
            
        inOrderSeq = list()
        inOrder(root)
        return build(0,len(inOrderSeq)-1)

653. 两数之和 IV - 输入二叉搜索树（model-VI 扩展）

题目链接：653. 两数之和 IV - 输入二叉搜索树
题目大意：给定一个二叉搜索树 root 和一个目标结果 k，如果二叉搜索树中存在两个元素且它们的和等于给定的目标结果，则返回 true。

例如：

输入: root = [5,3,6,2,4,null,7], k = 9
输出: true

输入: root = [5,3,6,2,4,null,7], k = 28
输出: false

• 解题思路：DFS
• 时间复杂度：$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 __init__(self):
        self.s = set()

    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
        if root is None: return False
        if k-root.val in self.s:
            return True
        self.s.add(root.val)
        return self.findTarget(root.left,k) or self.findTarget(root.right,k)

112. 路径总和**（model-VII 路径）

题目链接：112. 路径总和
题目大意：给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。

例如：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true
解释：等于目标和的根节点到叶节点路径如上图所示。

• 解题思路： DFS 与653. 两数之和 IV - 输入二叉搜索树相近 这里注意叶子结点的判断方式 非常典型 后续会用到很多。
• 时间复杂度：$O(N)$ 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 hasPathSum(self, root: Optional[TreeNode], tSum: int) -> bool:
        if root is None: return False
        if root.left is None and root.right is None: return root.val == tSum
        return self.hasPathSum(root.left,tSum-root.val) or \
        self.hasPathSum(root.right,tSum-root.val)

257. 二叉树的所有路径 **（model-VII 路径）

题目链接：257. 二叉树的所有路径
题目大意：给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。叶子节点 是指没有子节点的节点。

例如：

输入：root = [1,2,3,null,5]
输出：["1->2->5","1->3"]

• 解题思路： DFS 或 BFS。
• 时间复杂度：$O(N^2)$ N为二叉树的结点数
• 空间复杂度：$O(N^2)$

方法（一）

# 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 binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:

        def dfs(root:Optional[TreeNode],path:str) -> None:
            if root: 
                path += str(root.val)   
                if root.left is None and root.right is None:
                    paths.append(path) 
                else:
                    path += '->' 
                    dfs(root.left,path)
                    dfs(root.right,path)
                
        paths = list()
        dfs(root,"")
        return paths

方法（二）

# 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 binaryTreePaths(self, root: Optional[TreeNode]) -> List[str]:
      
        paths = list()
        if root is None: return paths
        q,qPath = list([root]),list([str(root.val)])
        while q:
            node,path = q.pop(),qPath.pop()
            if node.left is None and node.right is None:
                paths.append(path)
            else:
                if node.left:
                    q.append(node.left)
                    qPath.append(path + '->' + str(node.left.val))
                if node.right:
                    q.append(node.right)
                    qPath.append(path + '->' + str(node.right.val))
        return paths

129. 求根节点到叶节点数字之和（model-VII 路径）

题目链接：129. 求根节点到叶节点数字之和
题目大意：给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。
每条从根节点到叶节点的路径都代表一个数字：

• 例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。
  计算从根节点到叶节点生成的 所有数字之和 。
  叶节点 是指没有子节点的节点。

例如：

输入：root = [1,2,3]
输出：25
解释：
从根到叶子节点路径 1->2 代表数字 12
从根到叶子节点路径 1->3 代表数字 13
因此，数字总和 = 12 + 13 = 25

• 解题思路： 与 257. 二叉树的所有路径 一样的思路，不过对于结点的值处理手段不同。
• 时间复杂度：$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 sumNumbers(self, root: Optional[TreeNode]) -> int:
        # DFS
        def dfs(node: Optional[TreeNode],num: int) -> None:
            if node:
                num = 10*num + node.val
                if node.left is None and node.right is None:
                    paths.append(num)
                else:
                    dfs(node.left,num)
                    dfs(node.right,num)

        paths = list()
        num = 0
        dfs(root,num)
        # print(paths)
        return sum(paths)

113. 路径总和 II（model-VII 路径）

题目链接：113. 路径总和 II
题目大意：给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

• 叶子节点 是指没有子节点的节

例如：

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：[[5,4,11,2],[5,8,4,5]]

• 解题思路： DFS 这里注意了 append 函数 只能添加单个元素 一定要用 [:] 复制整个数组元素。
• 时间复杂度：$O(N^2)$ 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: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        
        def dfs1(root:Optional[TreeNode],tSum: int) -> bool:
            if root is None: return False
            if root.left is None and root.right is None:
                return root.val == tSum
            return dfs1(root.left,tSum-root.val) or dfs1(root.right,tSum-root.val)

        
        def dfs2(root:Optional[TreeNode],tSum: int) -> None:
            if root:
                path.append(root.val)
                tSum -= root.val
                if root.left is None and root.right is None and tSum == 0:
                    # 搞明白 append 加入的是一个元素 需要[:]
                    paths.append(path[:])
                dfs2(root.left,tSum)
                dfs2(root.right,tSum)
                path.pop()

        paths = list()
        path = list()
        if dfs1(root,targetSum):
            dfs2(root,targetSum)
            return paths
        else:
            return []

437. 路径总和 III（model-VII 路径）

题目链接：437. 路径总和 III
题目大意：
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。

• 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

例如：

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。

• 解题思路： 双重 DFS
• 时间复杂度：$O(N^2)$ 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: Optional[TreeNode], targetSum: int) -> int:

        def rootSum(node: Optional[TreeNode],tSum: int) -> int:
            if node is None: return 0
            res = 0
            if node.val == tSum:
                res += 1
            res += rootSum(node.left,tSum-node.val) 
            res += rootSum(node.right,tSum-node.val)
            return res

        if root is None: return 0
        ans = rootSum(root,targetSum)
        ans += self.pathSum(root.left,targetSum)
        ans += self.pathSum(root.right,targetSum)
        return ans

124. 二叉树中的最大路径和（model-VII 路径）

题目链接：124. 二叉树中的最大路径和
题目大意：路径 被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。

• 路径和 是路径中各节点值的总和。给你一个二叉树的根节点 root ，返回其 最大路径和 。

例如：

输入：root = [1,2,3]
输出：6
解释：最优路径是 2 -> 1 -> 3 ，路径和为 2 + 1 + 3 = 6

输入：root = [-10,9,20,null,null,15,7]
输出：42
解释：最优路径是 15 -> 20 -> 7 ，路径和为 15 + 20 + 7 = 42

• 解题思路： DFS 注意 return 以及 P 的求解
• 时间复杂度：$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 __init__(self):
        self.maxN = -float('inf')

    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        
        def dfs(node: Optional[TreeNode]) -> int:
            if node is None: return 0

            L = max(dfs(node.left),0)
            R = max(dfs(node.right),0)
            P = node.val + L + R 
            self.maxN = max(self.maxN,P)
            return node.val + max(L,R)

        dfs(root)
        return self.maxN

总结

   努力 奋斗！ 这部分内容那个 主要是和 二叉搜索树、平衡二叉树、二叉树路径问题相关，非常的基础。解决树的问题，DFS 首选项，要多学多思考。