LeetCodeCampsDay17二叉树part05

包含二叉搜索树的判断与搜索；以及合并二叉树的应用，最大二叉树的创建

654. 最大二叉树

https://leetcode.cn/problems/maximum-binary-tree/

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:

  1. 创建一个根节点，其值为 nums 中的最大值。
  2. 递归地在最大值 左边 的 子数组前缀上 构建左子树。
  3. 递归地在最大值 右边 的 子数组后缀上 构建右子树。

返回 nums 构建的 *最大二叉树* 。

示例 1：

img

1
2
3
4
5
6
7
8
9
10
11
12
输入：nums = [3,2,1,6,0,5]
输出：[6,3,5,null,2,0,null,null,1]
解释：递归调用如下所示：
- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
    - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
        - 空数组，无子节点。
        - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
            - 空数组，无子节点。
            - 只有一个元素，所以子节点是一个值为 1 的节点。
    - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
        - 只有一个元素，所以子节点是一个值为 0 的节点。
        - 空数组，无子节点。

示例 2：

img

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

提示：

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000
  • nums 中的所有整数 互不相同

递归思路

  1. 使用递归解决：
    1. 终止条件，当发现叶子节点时返回这个节点，即len(nums)==1就返回构造的节点
    2. 输入输出：输入列表，输出根节点
    3. 单层逻辑：先找到列表中最大值，它为root节点，再以root为界限，找左、右子树（前提是有左、右子树），需要加个对rootIndex的判断；对nums的划分有点儿像之前做的根据前/中序列构造二叉树

递归代码

  • 时间复杂度O(N)
  • 空间复杂度O(H)—最坏情况O(N)最好O(logN)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# 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.res = list()
    def traversal(self, nums: List[int]) -> Optional[TreeNode]:
        L = len(nums)
        # 终止条件是：发现叶子节点就直接返回
        if L == 1:
            return TreeNode(nums[0])

        # 找最大值
        maxIndex = 0
        for i in range(L):
            if nums[i] >= nums[maxIndex]:
                maxIndex = i
        root = TreeNode(nums[maxIndex])
        # 注意，maxIndex至少要有左子树和右子树
        if maxIndex > 0:
            leftTree = self.traversal(nums[:maxIndex])
            root.left = leftTree
        if maxIndex < L - 1:
            rightTree = self.traversal(nums[maxIndex + 1:])
            root.right = rightTree
        
        return root

    def constructMaximumBinaryTree(self, nums: List[int]) -> Optional[TreeNode]:
        # 注意层序顺序返回结果
        from collections import deque
        que = deque()

        if len(nums)==0:
            return []
        root = self.traversal(nums)

        return root

700. 二叉搜索树中的搜索

https://leetcode.cn/problems/search-in-a-binary-search-tree/

给定二叉搜索树（BST）的根节点 root 和一个整数值 val。

你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 null 。

示例 1:

img

1
2
输入：root = [4,2,7,1,3], val = 2
输出：[2,1,3]

示例 2:

img

1
2
输入：root = [4,2,7,1,3], val = 5
输出：[]

提示：

  • 树中节点数在 [1, 5000] 范围内
  • 1 <= Node.val <= 107
  • root 是二叉搜索树
  • 1 <= val <= 107

递归思路

  1. BST树特点是可以使用类似二分查找，若val小于当前值就在当前node的左子树找；否则在右子树找
  2. 输入输出：输入node和val，输出节点
  3. 终止条件：当前node为空
  4. 单层逻辑：若val小于当前值就在当前node的左子树找；否则在右子树找，如果相等就返回node

递归代码

  • 时间复杂度O(h) – 最好O(logN)，最坏O(N)
  • 空间复杂度O(h) – 最好O(logN)，最坏O(N)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 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 findTarget(self, node: TreeNode, val: int) -> TreeNode:
        if not node:
            return None
        
        if node.val > val:
            return self.findTarget(node.left, val)
        elif node.val < val:
            return self.findTarget(node.right, val)
        return node
        
    def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        # BST特点是可以使用类似二分查找，若val小于当前值就在左子树找；否则在右子树找
        return self.findTarget(root, val)

迭代思路

一提到二叉树遍历的迭代法，可能立刻想起使用栈来模拟深度遍历，使用队列来模拟广度遍历。

对于二叉搜索树可就不一样了，因为二叉搜索树的特殊性，也就是节点的有序性，可以不使用辅助栈或者队列就可以写出迭代法。

对于一般二叉树，递归过程中还有回溯的过程，例如走一个左方向的分支走到头了，那么要调头，在走右分支。

而对于二叉搜索树，不需要回溯的过程，因为节点的有序性就帮我们确定了搜索的方向。

例如要搜索元素为3的节点，我们不需要搜索其他节点，也不需要做回溯，查找的路径已经规划好了。

中间节点如果大于3就向左走，如果小于3就向右走，如图：

img

迭代代码

  • 时间复杂度O(h) – 最好O(logN)，最坏O(N)
  • 空间复杂度O(h) – 最好O(logN)，最坏O(N)
1
2
3
4
5
6
7
8
9
10
def searchBST(self, root: Optional[TreeNode], val: int) -> Optional[TreeNode]:
        # BST的迭代
        while root is not None:
            if root.val == val:
                return root
            elif root.val < val:
                root = root.right
            else:
                root = root.left
        return root

98. 验证二叉搜索树

https://leetcode.cn/problems/validate-binary-search-tree/

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

  • 节点的左子树只包含 小于 当前节点的数。
  • 节点的右子树只包含 大于 当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

img

1
2
输入：root = [2,1,3]
输出：true

示例 2：

img

1
2
3
输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

  • 树中节点数目范围在[1, 104] 内
  • -231 <= Node.val <= 231 - 1

中序迭代思路

  1. 先用中序遍历输出到个数组中，再看数组是否是单调的
  2. 验证是否单调就找个maxIndex，如果后一个值大于maxIndex就更新maxIndex并继续搜索；否则就直接return False

中序迭代代码

  • 时间复杂度O(N^2) — 主要是后面验证是否单调递增浪费时间
  • 空间复杂度O(N)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# 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: Optional[TreeNode]) -> bool:
        # 按中序遍历，输出的应该是单调增长的

        stack = [(root, False)] if root else []
        res = list()
        while stack:
            node, visited = stack.pop()
            if visited:
                res.append(node.val)
            else:
                if node.right:
                    stack.append([node.right, False])
                stack.append([node, True])
                if node.left:
                    stack.append([node.left, False])
        #print(res)
        #rturn all(x < y for x, y in zip(res, res[1:]))                
        maxIndex = 0
        L = len(res)
        for i in range(1, L):
            if res[i] > res[maxIndex]:
                maxIndex = i
            else:
                return False
        return True

中序迭代思路二

  1. 添加一个pre节点，在每次对visited==True时进行pre与当前节点的判断，如果pre大于或等于node，则一定有问题！
  2. 好处是不需要额外数组装结果，中序遍历过程中就能判断是否有问题

没错的，使用pre大于或等于node进行判断就行，因为目前是中序输出，不管下面哪种情况，都可以用pre大于或等于node来判断出False

image-20250711201453775

统一中序迭代代码二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def isValidBST(self, root: Optional[TreeNode]) -> bool:
    # 按中序遍历，输出的应该是单调增长的

    stack = [(root, False)] if root else []
    pre = None
    while stack:
        node, visited = stack.pop()
        if visited:
            if pre and pre.val >= node.val:
                return False
            pre = node
        else:
            if node.right:
                stack.append([node.right, False])
            stack.append([node, True])
            if node.left:
                stack.append([node.left, False])
    
    return True

普通中序迭代代码三

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 stack = list()
 cur = root
 pre = None
# cur先一路干到最底层的左子树左叶子节点
 while cur or stack:
     if cur:
         stack.append(cur)
         cur = cur.left
     # 到达最左节点后，开始处理栈顶节点
     else:
       	# 最底层的左子树左叶子节点开始输出，append到
         cur = stack.pop()
         if pre and cur.val <= pre.val:
             return False
         pre = cur
         # 取栈顶元素右节点
         cur = cur.right
 return True

617. 合并二叉树

https://leetcode.cn/problems/merge-two-binary-trees/

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

注意: 合并过程必须从两个树的根节点开始。

示例 1：

img

1
2
输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]

示例 2：

1
2
输入：root1 = [1], root2 = [1,2]
输出：[2,2]

提示：

  • 两棵树中的节点数目在范围 [0, 2000] 内
  • -104 <= Node.val <= 104

递归思路

  1. 本题和对称二叉树有点儿像
  2. 终止条件：如果都空就返回None；哪个空就返回另一个；
  3. 输入输出：输入两个节点，输出合并后的节点
  4. 单层逻辑：只有都不空，才创建root节点并将两个节点相加，随后创建root的左、右子树

img

递归代码

  • 时间复杂度O(N+M)
  • 空间复杂度O(H) 其中 H 是两个树中高度的最大值。主要由递归调用栈引起
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# 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, node1, node2) -> TreeNode:
        if not node1 and node2:
            return node2
        elif not node2 and node1:
            return node1
        elif not node1 and not node2:
            return None
        else:
            root = TreeNode(node1.val + node2.val)

        leftTree = self.buildTree(node1.left, node2.left)
        rightTree = self.buildTree(node1.right, node2.right)

        root.left = leftTree
        root.right = rightTree

        return root


    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        # 树长度不用相同，使用递归
        return self.buildTree(root1, root2)

迭代思路

  1. 使用层序，和对称二叉树有点儿像，每次处理两个节点；每次添加两个节点进去，弹出两个节点出来
  2. 但本题可以直接拿其中一个root当成结果，比如root1
  3. 每次判断时，如果只有当node1和node2的左子树都不为空，才添加到que；否则如果node1.left为空，则让node1.left等于node2.left（这里隐藏了一条代码，如果node2.left为空，则让node1.left等于node1.left，即不变）；对node1和node2的右子树同样这样操作
  4. 最终返回root1即可

迭代代码

  • 时间复杂度O(N+M)
  • 空间复杂度O(H) 其中 H 是两个树中高度的最大值。主要由递归调用栈引起
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
    # 迭代版，使用层序
    from collections import deque
    que = deque()
    if not root1:
        return root2
    if not root2:
        return root1
    que.append(root1)
    que.append(root2)
    while que:
        L = len(que)
        node1 = que.popleft()
        node2 = que.popleft()

        node1.val += node2.val

        if node1.left and node2.left:
            que.append(node1.left)
            que.append(node2.left)
        if node1.right and node2.right:
            que.append(node1.right)
            que.append(node2.right)

        if not node1.left and node2.left:
            node1.left = node2.left

        if not node1.right and node2.right:
            node1.right = node2.right

    return root1

103. 二叉树的锯齿形层序遍历

https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

示例 1：

img

1
2
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]

示例 2：

1
2
输入：root = [1]
输出：[[1]]

示例 3：

1
2
输入：root = []
输出：[]

提示：

  • 树中节点数目在范围 [0, 2000] 内
  • -100 <= Node.val <= 100

层序迭代思路

  1. 按层序遍历即可，先把每层元素全添加到level，再按奇偶反转level内部,再添加到res

层序迭代代码

  • 时间复杂度O(N)
  • 空间复杂度O(H)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
# 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 zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        # 先全添加到level，再按奇偶反转level内部,再添加到res
        from collections import deque
        que = deque()
        if not root:
            return []
        que.append(root)
        res = list()
        countLevel = 1
        while que:
            L = len(que)
            level = list()
            for i in range(L):
                node = que.popleft()
                level.append(node.val)
                if node.left:
                    que.append(node.left)
                if node.right:
                    que.append(node.right)
            if countLevel % 2 == 0:
                level = level[::-1]
            res.append(level)
            countLevel += 1
        return res