二叉搜索树

二叉搜索树是一种特殊的树形结构，若它的左子树不空，则左子树上所有结点的值均小于它的的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值

# 练习题

特点

具有下列性质的：若它的左子树不空，则左子树上所有结点的值均小于它的的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值

# 1.1. 不同的二叉搜索树 II (opens new window)

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

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

1 <= n <= 8

# 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]]:
      """
      二叉搜索树
      1. 左节点>根节点>右节点
      考虑当i为根节点是，可能的左子树为【i,i-1]
      可能的右子树为
      """
      def generateTrees(start,end):
          if start>end:
              return [None]
          allTrees = list()
          for i in range(start, end+1):
              # 获取可能所有左子树
              leftTree = generateTrees(start, i-1)
              rightTree = generateTrees(i+1, end)
              for left in leftTree:
                  for right in rightTree:
                      cur = TreeNode(val=i)
                      cur.left=left
                      cur.right = right 
                      allTrees.append(cur)
          return allTrees
              

      return generateTrees(1, 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
33
34

/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func generateTrees(n int) []*TreeNode {
  if n == 0 {
      return nil
  }
  return generateTree(1, n)
}

func generateTree(start, end int) []*TreeNode{
  if start > end{
      return []*TreeNode{nil}
  }
  allTrees := []*TreeNode{}
  for i:= start;i<=end;i++{
      leftNodes := generateTree(start, i-1)
      rightNodes := generateTree(i+1, end)
      for _,left := range leftNodes{
          for _, right := range rightNodes{
              cur := &TreeNode{Val:i, Left:left, Right:right}
              allTrees = append(allTrees, cur)
          }
      }
  }
  return allTrees
}

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

// Make sure to add code blocks to your code group

# 1.2. 验证二叉搜索树 (opens new window)

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

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

节点的左

子树

只包含

小于

当前节点的数。

节点的右子树只包含大于当前节点的数。

所有左子树和右子树自身必须也是二叉搜索树。

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

树中节点数目范围在[1, 104] 内

-231 <= Node.val <= 231 - 1

# 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,ret = list(), list()
      while root or stack:
          while root:
              stack.append(root)
              root = root.left
          cur = stack.pop()
          if ret and cur.val<=ret[-1]:
              return False
          ret.append(cur.val)
          root = cur.right
      return True

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

/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func isValidBST(root *TreeNode) bool {
  // 二叉搜索树的遍历和中序遍历的顺序一支
  ret, stack := make([]int, 0), make([]*TreeNode, 0)
  for root != nil || len(stack)>0 {
      for root !=nil{
          stack = append(stack, root)
          root = root.Left
      }
      cur := stack[len(stack)-1]
      stack = stack[:len(stack)-1]
      root = cur.Right
      if len(ret) == 0{
          ret = append(ret, cur.Val)
          continue
      }
      if ret[len(ret)-1] >= cur.Val{
          return false
      }
      ret = append(ret, cur.Val)
  }
  return true
}

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

// Make sure to add code blocks to your code group

# 1.3 恢复二叉搜索树 (opens new window)

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

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

树上节点的数目在范围 [2, 1000] 内

-231 <= Node.val <= 231 - 1

**进阶：**使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用 O(1) 空间的解决方案吗？

# 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 recoverTree(self, root: Optional[TreeNode]) -> None:
      """
      Do not return anything, modify root in-place instead.
      """
      # 二叉搜索树的特性，左子树小于右子树
      firstNode = None
      secondNode = None
      stack, ret = list(), list()
      while root or stack:
          while root:
              stack.append(root)
              root = root.left
          cur = stack.pop()
          if ret:
              if not firstNode and cur.val < ret[-1].val:
                  firstNode = ret[-1]
              if firstNode and cur.val < ret[-1].val:
                  # if cur.val <= ret[-1].val:
                  secondNode = cur
          ret.append(cur)
          root= cur.right
      firstNode.val, secondNode.val = secondNode.val, firstNode.val

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.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func recoverTree(root *TreeNode)  {
  // 找到错误交换的两个节点，交换两个节点的val
  // 二叉搜索树的特性是所有左节点小于根节点，所有右节点大于根节点
  // 中序遍历的顺序就是二叉搜索树排序后的结果
  var firstNode *TreeNode
  var secondNode *TreeNode
  stack := make([]*TreeNode, 0)
  var preNode *TreeNode
  for root != nil || len(stack)>0{
      for root != nil{
          stack = append(stack, root)
          root = root.Left
      }
      cur := stack[len(stack)-1]
      stack = stack[:len(stack)-1]
      if preNode != nil && preNode.Val >=cur.Val{
          if firstNode == nil{
              firstNode = preNode
              secondNode = cur
          }else{
              secondNode = cur
              break
          }
          
      }        
      root = cur.Right
      preNode = cur
  }
  firstNode.Val, secondNode.Val = secondNode.Val, firstNode.Val

}

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

// Make sure to add code blocks to your code group

笔记

注意在golang的代码里,firstNode==nil时,需要同时给firstNode和second同时赋值,表示,如果找firstNode后,由于preNode赋值给了firstSecond,此时cur有可能是secondNode

# 1.4. 相同的树 (opens new window)

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1：
输入：p = [1,2,3], q = [1,2,3]
输出：true
1
2
示例 2：
输入：p = [1,2], q = [1,null,2]
输出：false
1
2
示例 3：
输入：p = [1,2,1], q = [1,1,2]
输出：false
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 isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
      """
      广度优先遍历
      """
      if (not p) and (not q):
          return True

      if (not p ) ^ (not q):
          return False
      

      queue1 = collections.deque([p])
      queue2 = collections.deque([q])

      while queue1 or queue2:
          cur1 = queue1.popleft()
          cur2 = queue2.popleft()
          if (not cur1) ^ (not cur2):
              return False
          if cur1 and cur2:
              if cur1.val != cur2.val:
                  return False
              left1 = cur1.left
              left2 = cur2.left
              if (not left1) ^ (not left2):
                  return False
              right1 = cur1.right
              right2 = cur2.right
              if (not right1) ^(not right2):
                  return False
              queue1.append(left1)
              queue2.append(left2)
              queue1.append(right1)
              queue2.append(right2)
      return True

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
42

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
  def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
      """
      深度优先遍历，看是否值和结构是否相同
      """
      stack1, stack2 = list(), list()
      if (not q) and (not p):
          return True
      if (not q) ^ (not p):
          return False
      while p or stack1 or q or stack2:
          while p or q:
              if (not p) ^ (not q):
                  return False
              stack1.append(p)
              stack2.append(q)
              p = p.left
              q = q.left
              if (not p) ^ (not q):
                  return False
          cur1 = stack1.pop()
          cur2 = stack2.pop()
          if (not cur1) ^ (not cur2):
              return False
          if cur1 and cur2:
              if cur1.val != cur2.val:
                  return False
              if (not cur2.right) ^ (not cur1.right):
                  return False
          p = cur1.right
          q = cur2.right
      return True

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

/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func isSameTree(p *TreeNode, q *TreeNode) bool {
  // 广度优先遍历解法
  queue1, queue2 := []*TreeNode{p}, []*TreeNode{q}
  for ;len(queue1)>0 || len(queue2)>0;{
      cur1 := queue1[len(queue1)-1]
      cur2 := queue2[len(queue2)-1]
      queue1 = queue1[:len(queue1)-1]
      queue2 = queue2[:len(queue2)-1]
      // 如果两个不同时为nil
      if (cur1==nil)!=(cur2==nil){
          return false
      }
      // 如果两个都为nil，这里上面判断了不同时为nil、
      // 这里要么都为nil， 要么都不为nil,所以只是判断一个就够了
      if cur1 == nil{
          continue
      }
      if cur1.Val != cur2.Val{
          return false
      }
      left1 := cur1.Left
      left2 := cur2.Left
      right1 := cur1.Right
      right2 := cur2.Right
      if (left1==nil)!=(left2==nil) || (right1==nil)!=(right2==nil){
          return false
      }
      queue1 = append(queue1, left1)
      queue1 = append(queue1, right1)
      queue2 = append(queue2, left2)
      queue2 = append(queue2, right2)
  }
  return true

}

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
42
43

/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func isSameTree(p *TreeNode, q *TreeNode) bool {
  // 深度优先解法
  stack1 := make([]*TreeNode, 0)
  stack2 := make([]*TreeNode, 0)
  for p != nil || q != nil || len(stack1)>0 || len(stack2)>0{
      for p !=nil || q != nil{
          stack1 = append(stack1, p)
          stack2 = append(stack2 ,q)
          if (p == nil) != (q==nil){
              return false
          }
          p = p.Left
          q = q.Left
          if (p ==nil) != (q==nil){
              return false
          }
      }
      cur1 := stack1[len(stack1)-1]
      cur2 := stack2[len(stack2)-1]
      if cur1.Val != cur2.Val{
          return false
      }
      q = cur1.Right
      stack1 = stack1[:len(stack1)-1]
      p = cur2.Right
      stack2 = stack2[:len(stack2)-1]

  }
  return true
}

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

// Make sure to add code blocks to your code group

编辑

上次更新: 2024/12/31 14:23:38

← 二叉树遍历二叉树属性→