递归算法解决二叉树问题
洪笳淏 Lv4
 2021-08-18 18:00:00      

递归算法的原理

  一个递归函数的调用类似于多个函数的嵌套调用，只不过调用函数和被调函数都是同一个函数。在解决递归问题时，最重要的是不要陷入递归的逻辑中去，视角要以一个节点为根基来考虑整个问题。递归调用时内部的执行过程如下:

  1. 首先为递归调用建立一个工作栈，其结构包括值参、局部变量和返回地址；
  2. 每次执行递归调用前，把递归函数的值参、局部变量的当前值以及调用后的返回地址压栈；
  3. 每次递归调用结束后，将栈顶元素推出，使相应的值参和局部变量恢复为调用前的值，然后转向返回地址的位置继续执行。

  在明确了递归函数的执行过程后，只要把握好如下3个步骤即可：

  1. 明确递归函数的作用；
  2. 明确终止条件和相应的解决办法；
  3. 找出函数的等价关系式，提取重复的逻辑缩小问题规模。

递归三步走

1.明确函数功能

  首先要确定这个函数的具体功能是什么？它的参数有哪些？它的全局变量是什么？递归的时候要根据题目的要求设置函数功能，再根据函数功能来设置函数的参数。

  方法参数：这个方法的参数最好由当前阶段的状态决定。

  返回数据：返回数据是我们遇到递归出口之后，需要告诉前一步递归的信息数据。

注意：

  • 递归函数的返回值最好设置为单个元素，比如说一个节点或者一个数值，告诉前一步递归我们现在的结果数据即可；
  • 如果返回值是数组的话，我们将无法从中提取到任何有效信息来进行操作；
  • 如果结果需要数组的话，我们可以将数组作为公共变量返回值为void，我们在方法体里面操作数组即可。

2.寻找递归出口

  在递归函数的一开始，我们应该思考什么时候该结束递归。因此，递归一定要有结束条件，不然会永远的递归下去。递归出口一般为某深度或叶子结点，或非叶子结点（包括根节点）、所有节点等。决定递归出去后要执行的操作。由于我们的节点状态可能需要多个参数来表示，所以我们的递归出口可能并不唯一，可能需要为每一个转台参数安排一个递归出口，确保我们的递归能够确实有效地出去。

特别注意的：每次提交数组的集合（即list(dst())）的时候，要创建一个新的数组copy()来存放结果数组dst()，不然后面操作的都是加入集合list()的那个数组dst()。

  我们的递归出口并不一定都是在最开头的位置，我们一般在最开头设置递归出口是希望递归能以最快的速度出去；但是有时候我们在对当前节点进行一些相关处理操作之后我们就希望判断一下能不能递归出口，所以递归出口有可能是在代码中间的，大家需要灵活应用。在这一步，我们需要思考题目需要的解在哪里？是在某一具体的深度、还是在叶子结点、还是在非叶子结点（包括根节点）、还是在每个节点、还是在从跟结点到叶子结点的路径？

  • 在某一具体深度：if depth >= n
  • 在每个节点：if root != nil

3.找出递推关系

  类比于数学归纳法。算n的阶乘：

  • 初始条件：f(1) = 1
  • 递推关系式：f(n) = f(n-1) * n

递归关系：

  • 递：f(n) = n * f(n-1)，将f(n)→f(n-1)了。这样，问题就由n缩小为了n-1，并且为了原函数f(n)不变，我们需要让f(n-1)乘以n。就这样慢慢从f(n),f(n-1)“递”到f(1)。
  • 归：这样就可以从n=1，一步一步“归”到n=2,n=3,...
1
2
3
4
5
6
7
func (n int) int {
  if n == 1 { // 递归出口
    return 1
  }
  
  return f(n-1)*n
}

运用递归的二叉树算法题

  二叉树的递归框架无外乎二叉树的三种遍历方式：前序遍历、中序遍历、后序遍历。在想好递归出口后，就要考虑采用何种方式来遍历整个二叉树有助于我们解决问题。解决这类问题的核心难点是不要深入进递归细节中，不要把自己的大脑当计算机来用！只要着眼于根节点，在设置好递归出口的前提下就能顺利地解题。

1.直接递归遍历整个二叉树后返回根节点

  此类问题不需要引入一个用于记录和更新极值结果的中间全局变量，只需要对二叉树本身进行操作，所以在传入的方法参数上比较简单，只需要关注于节点本身（以根节点为视角和着眼点）。大多数题目都是针对树结构进行性重建，查找或删除等操作。

剑指 Offer 07. 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例 1:

avatar

1
2
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

示例 2:

1
2
Input: preorder = [-1], inorder = [-1]
Output: [-1]

限制：

1
0 <= 节点个数 <= 5000

解题思路：

对于任意一颗树而言，前序遍历的形式总是：

[ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
即根节点总是前序遍历中的第一个节点。而中序遍历的形式总是：

[ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]

  只要我们在中序遍历中定位到根节点，那么我们就可以分别知道左子树和右子树中的节点数目。由于同一颗子树的前序遍历和中序遍历的长度显然是相同的，因此我们就可以对应到前序遍历的结果中，对上述形式中的所有左右括号进行定位。这样以来，我们就知道了左子树的前序遍历和中序遍历结果，以及右子树的前序遍历和中序遍历结果，我们就可以递归地对构造出左子树和右子树，再将这两颗子树接到根节点的左右位置。

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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func buildTree(preorder []int, inorder []int) *TreeNode {
  if len(preorder) == 0 {  // 递归出口
    return nil
  }
		
  root := &TreeNode{preorder[0],nil,nil} // 着眼于根节点
  for i:=0; i<len(inorder); i++ {  // 找到在中序遍历数组中根节点的位置
  	if inorder[i] == preorder[0] {
    	break
      }
  }
  	
  root.Left = buildTree(preorder[1:i+1], inorder[:i])  // 构建左子树
  root.Right = buildTree(preorder[i+1:], inorder[i+1:])  // 构建右子树
  return root
}

106. 从中序与后序遍历序列构造二叉树

根据一棵树的中序遍历与后序遍历构造二叉树。

注意:
你可以假设树中没有重复的元素。

例如，给出

1
2
中序遍历 inorder = [9,3,15,20,7]
后序遍历 postorder = [9,15,7,20,3]

返回如下的二叉树：

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7
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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func buildTree(inorder []int, postorder []int) *TreeNode {
  if len(postorder) == 0 {
  	return nil
  }
  	
  root := &TreeNode{postorder[len(postorder)-1],nil,nil}
  i:=0
  for ; i<len(inorder); i++ {
    if inorder[i] == postorder[len(postorder)-1] {
      break
    }
  }
  root.Left = build(inorder[:i],postorder[:i])
  root.Right = build(inorder[i+1:],postorder[i:len(postorder)-1])
 
  return root
}

226. 翻转二叉树

翻转一棵二叉树。

示例：

输入：

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

输出：

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

废话少说，直接看代码吧，简单题。

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.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func invertTree(root *TreeNode) *TreeNode {
  if root == nil {
  	return nil
  }
  
  left := invertTree(root.Left)
  right := invertTree(root.Right)  // 后序遍历
  root.Left = right
  root.Right = left
  
  return root
}

104. 二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

返回它的最大深度 3 。

简单题，直接上代码。

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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func maxDepth(root *TreeNode) int {
  if root == nil {  // 递归出口，空节点返回深度0
    return 0
  }
  
  left := maxDepth(root.Left)  // 左子树深度
  right := maxDepth(root.Right)  // 右子树深度
  
  return 1+max(left,right)  // 返回最终深度=左右子树最大深度+1
}

func max(a,b int) int {
  if a>=b {
  	return a
  }
  return b
}

101. 对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

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

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

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

解题思路：

  如果同时满足下面的条件，两个树互为镜像：

  • 它们的两个根结点具有相同的值；
  • 每个树的右子树都与另一个树的左子树镜像对称。

  我们可以实现这样一个递归函数，通过「同步移动」两个指针的方法来遍历这棵树，p 指针和 q 指针一开始都指向这棵树的根，随后 p 右移时，q 左移；p 左移时，q 右移。每次检查当前 p 和 q 节点的值是否相等，如果相等再判断左右子树是否对称。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSymmetric(root *TreeNode) bool {
   return check(root, root)
}

func check(q,p *TreeNode) bool {
  if q == nil && p == nil {  // p，q均为空节点，返回true
    return true
  }

  if q == nil || p == nil { // p，q只有其中一者为空节点，返回false
  	return false
  }
	// 1.p，q节点的值相等；2.q的左节点与p的右节点相等；3.q的右节点与p的左节点相等。
  return q.Val == p.Val && check(q.Left,p.Right) && check(q.Right,p.Left)
}

236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

示例 1：

avatar

1
2
3
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。

示例 2：

avatar

1
2
3
输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。

示例 3：

1
2
输入：root = [1,2], p = 1, q = 2
输出：1

提示：

1
2
3
4
5
树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。

解题思路：

  我们递归遍历整棵二叉树，定义 $f_{x}$ 表示 $x$ 节点的子树中是否包含 $p$ 节点或 $q$ 节点，如果包含为true,否则为false。那么符合条件的最近公共祖先 $x$ 一定满足如下条件：

$\left(f_{\text {lson }} & & f_{\text {rson }}\right) |\left((x=p | x=q) & &\left(f_{\text {lson }} | f_{\text {rson }}\right)\right)$

其中 ${\text{lson}}$ 和 ${\text{rson}}$ 分别代表 $x$ 节点的左孩子和右孩子。$\left(f_{\text {lson }} & & f_{\text {rson }}\right)$ 说明左子树和右子树均包含 $p$ 节点或 $q$ 节点，如果左子树包含的是 $p$ 节点，那么右子树只能包含 $q$ 节点，反之亦然，因为 $p$ 节点和 $q$ 节点都是不同且唯一的节点，因此如果满足这个判断条件即可说明 $x$ 就是我们要找的最近公共祖先。再来看第二条判断条件，这个判断条件即是考虑了 $x$ 恰好是 $p$ 节点或 $q$ 节点且它的左子树或右子树有一个包含了另一个节点的情况，因此如果满足这个判断条件亦可说明 $x$ 就是我们要找的最近公共祖先。

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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
  if root == nil {
  	return nil
  }
  if root == p || root == q { // 当遇到p或q节点时剪枝，不再向下递，开始归
    return root
  }
  
  left := lowestCommonAncestor(root.Left,p,q)
  right := lowestCommonAncestor(root.Right,p,q) // 后序遍历的框架
  
  if left != nil && right != nil { // p,q节点分别在左右子树，当前节点即是共同祖先
    return root
  }
  
  if left == nil { // 左子树中不包含p，q节点，右子树包含其中之一，该节点本身是p，q中的另一个
    return right
  }
  
  return left // 右子树中不包含p，q节点，左子树包含其中之一，该节点本身是p，q中的另一个
}

617. 合并二叉树

给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。

你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，否则不为 NULL 的节点将直接作为新二叉树的节点。

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入: 
	Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
输出: 
合并后的树:
	     3
	    / \
	   4   5
	  / \   \ 
	 5   4   7

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

解题思路：

方法一：深度优先搜索

可以使用深度优先搜索合并两个二叉树。从根节点开始同时遍历两个二叉树，并将对应的节点进行合并。

两个二叉树的对应节点可能存在以下三种情况，对于每种情况使用不同的合并方式。

  • 如果两个二叉树的对应节点都为空，则合并后的二叉树的对应节点也为空；
  • 如果两个二叉树的对应节点只有一个为空，则合并后的二叉树的对应节点为其中的非空节点；
  • 如果两个二叉树的对应节点都不为空，则合并后的二叉树的对应节点的值为两个二叉树的对应节点的值之和，此时需要显性合并两个节点。
    对一个节点进行合并之后，还要对该节点的左右子树分别进行合并。这是一个递归的过程。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
	if root1 == nil {
  	return root2
  }
  if root2 == nil {
    return root1
  }

  root1.Val += root2.Val
  root1.Left = mergeTrees(root1.Left, root2.Left)
  root1.Right = mergeTrees(root1.Right, root2.Right)

  return root1
}

方法二：广度优先搜索

也可以使用广度优先搜索合并两个二叉树。首先判断两个二叉树是否为空，如果两个二叉树都为空，则合并后的二叉树也为空，如果只有一个二叉树为空，则合并后的二叉树为另一个非空的二叉树。

如果两个二叉树都不为空，则首先计算合并后的根节点的值，然后从合并后的二叉树与两个原始二叉树的根节点开始广度优先搜索，从根节点开始同时遍历每个二叉树，并将对应的节点进行合并。

使用三个队列分别存储合并后的二叉树的节点以及两个原始二叉树的节点。初始时将每个二叉树的根节点分别加入相应的队列。每次从每个队列中取出一个节点，判断两个原始二叉树的节点的左右子节点是否为空。如果两个原始二叉树的当前节点中至少有一个节点的左子节点不为空，则合并后的二叉树的对应节点的左子节点也不为空。对于右子节点同理。

如果合并后的二叉树的左子节点不为空，则需要根据两个原始二叉树的左子节点计算合并后的二叉树的左子节点以及整个左子树。考虑以下两种情况：

  • 如果两个原始二叉树的左子节点都不为空，则合并后的二叉树的左子节点的值为两个原始二叉树的左子节点的值之和，在创建合并后的二叉树的左子节点之后，将每个二叉树中的左子节点都加入相应的队列；
  • 如果两个原始二叉树的左子节点有一个为空，即有一个原始二叉树的左子树为空，则合并后的二叉树的左子树即为另一个原始二叉树的左子树，此时也不需要对非空左子树继续遍历，因此不需要将左子节点加入队列。

对于右子节点和右子树，处理方法与左子节点和左子树相同。

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
44
45
46
47
func mergeTrees(root1 *TreeNode, root2 *TreeNode) *TreeNode {
	q1 := []*TreeNode{root1}
 	q2 := []*TreeNode{root2}

  if root1 == nil {
  	return root2
  }
  if root2 == nil {
    return root1
  }

  root3 := &TreeNode{root1.Val+root2.Val,nil,nil}
  q3 := []*TreeNode{root3}

  for len(q1)>0 && len(q2)>0 {
    node1 := q1[0]
    q1 = q1[1:]
    node2 := q2[0]
    q2 = q2[1:]
    node3 := q3[0]
    q3 = q3[1:]

    if node1.Left != nil && node2.Left != nil {
    	q1 = append(q1, node1.Left)
      q2 = append(q2, node2.Left)
      node3.Left = &TreeNode{node1.Left.Val+node2.Left.Val,nil,nil}
      q3 = append(q3, node3.Left)
    } else if node1.Left == nil && node2.Left != nil {
      	node3.Left = node2.Left // node1没有左子树，直接用node2的左子树接到新树上
    } else if node1.Left != nil && node2.Left == nil {
        node3.Left = node1.Left // node2没有左子树，直接用node1的左子树接到新树上
    }

    if node1.Right != nil && node2.Right != nil {
    	q1 = append(q1, node1.Right)
      q2 = append(q2, node2.Right)
      node3.Right = &TreeNode{node1.Right.Val+node2.Right.Val,nil,nil}
      q3 = append(q3, node3.Right)
    } else if node1.Right == nil && node2.Right != nil {
      node3.Right = node2.Right // node1没有右子树，直接用node2的右子树接到新树上
    } else if node1.Right != nil && node2.Right == nil {
      node3.Right = node1.Right // node2没有右子树，直接用node1的右子树接到新树上
    }

  }
  return root3
}

2.返回bool类型的结果(一般要求对二叉树是否符合某种性质做判别)

  此类问题一般只在递归出口处可能返回true，而在一般节点的判别时只返回false的情形。返回true表明递的过程结束，然而后续的节点不一定判别完了，会出现不应该的剪枝的情况。可以直接返回false的情形是因为遇到了不符合要求的情况，下面的节点不用继续判断了，就直接返回false。一般而言有下面这样的模板：

1
2
3
4
5
6
7
8
9
10
11
12
13
func helper(root *TreeNode) bool {
	if root == nil { // 递归出口
  	return true
 	}
  if [判别情形1] {
    return false
  }
  if [判别情形2] {
    return false
  }
  ...
  return helper(root.Left) && helper(root.Right)
}

剑指 Offer 33. 二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。

参考以下这颗二叉搜索树：

1
2
3
4
5
    5
   / \
  2   6
 / \
1   3

示例 1：

1
2
输入: [1,6,3,2,5]
输出: false

示例 2：

1
2
输入: [1,3,2,6,5]
输出: true

提示：

  1. 数组长度 <= 1000

解题思路：

  二叉搜索树的后续遍历数组满足如下定义：

  • 后序遍历： [ 左子树 | 右子树 | 根节点 ] ，即遍历顺序为 “左、右、根” 。
  • 二叉搜索树定义： 左子树中所有节点的值 < 根节点的值；右子树中所有节点的值 > 根节点的值；其左、右子树也分别为二叉搜索树。

avatar

递归解析：

  • 递归出口：len(postorder)==0时，返回true。
  • 递：

  1. 划分左右子树： 遍历后序遍历的元素，寻找 第一个大于根节点 的节点，索引记为 flag。此时，可划分出左子树区间 [:flag] 、右子树区间 [flag,len(postorder)−1] 、根节点索引为len(postorder)-1 。

  2. 判断是否为二叉搜索树： 左子树区间 [0,flag−1] 内的所有节点都应 < postorder[len(postorder)-1]。而第 1.划分左右子树 步骤已经保证左子树区间的正确性，因此只需要判断右子树区间即可。

    右子树区间[flag,len(postorder)-1]内所有节点都应 > postorder[len(postorder)-1]。实现方式为遍历，当遇到 < postorder[len(postorder)-1]的节点则跳出。

  • 归： 所有子树都需正确才可判定正确，因此使用 与逻辑符 && 连接。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func verifyPostorder(postorder []int) bool {
	if len(postorder) == 0 { // 递归出口
  	return true
  } 

  i := 0
  for ; i<len(postorder); i++ {
  	if postorder[i] >= postorder[len(postorder)-1] {
    	break
    }
  }

  flag := i  // 用于记录左右子树分界处的索引号

  for ; i<len(postorder); i++ {
  	if postorder[i] < postorder[len(postorder)-1] {
    	return false  // 右子树出现小于根节点的数，直接返回false跳出递的过程
    }
 	}
    
  // 左右子树分别满足上述条件才返回true
  return verifyPostorder(postorder[:flag]) && verifyPostorder(postorder[flag:len(postorder)-1])
}

剑指 Offer 26. 树的子结构

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

例如:
给定的树 A:

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

给定的树 B：

1
2
3
  4 
 /
1

返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1：

1
2
输入：A = [1,2,3], B = [3,1]
输出：false

示例 2：

1
2
输入：A = [3,4,5,1,2], B = [4,1]
输出：true

限制：

1
0 <= 节点个数 <= 10000

解题思路：

  • 两个函数

    • isSubStructure()
      • 用于递归遍历 A 中的所有节点，并判断当前节点 A 是否与 B 的根节点相同，相同则调用 helper( ) 进一步校验
    • helper()
      • 用于校验 B 是否与 A 的一个子树拥有相同的结构和节点值

  • 函数内容

    • isSubStructure()

      • 如果当前节点 A == nil && B == nil ，返回true。
      • 如果当前节点 A == nil | | B == nil ，返回 false。（由题目可知，空树不是任意一个树的子结构）
      • 当在当前结点 A 中找到 B 的根节点时，进入helper () 递归校验
      • ret == false，说明 B 的根节点不在当前 A 中，进入 A 的左子树进行递归查找
      • ret 仍等于 false，则说明 B 的根节点不在当前 A 和左子树中，进入 A 的右子树进行递归查找。

    • helper()

      • 如果 B == nil ，说明 B 已遍历完，返回 true

      • 在 B != nil 的情况下，如果 A == nil ,说明 A 中节点不足以构成子结构 B ，返回 false

      • 如果 A.Val != B.Val，不满足节点值相等条件，返回 false

      • A.Val == B.Val 继续递归校验 A B 左子树和右子树的结构和节点是否相同

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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isSubStructure(A *TreeNode, B *TreeNode) bool {
    if A == nil || B == nil {
        return false
    }

    var ret bool
    if A.Val == B.Val {
        ret = helper(A, B)
    }
    if !ret { // B 的根节点不在当前 A 中，进入 A 的左子树进行递归查找
        ret = isSubStructure(A.Left, B)
    }
    if !ret { // ret 仍等于 false，则说明 B 的根节点不在当前 A 和左子树中，进入 A 的右子树进行递归查找。
        ret = isSubStructure(A.Right, B)
    }
    return ret

}

func helper(A *TreeNode, B *TreeNode) bool {
    if B == nil { // 如果 B == nil ，说明 B 已遍历完，返回 true
        return true
    }
    if A == nil { // 在 B != nil 的情况下，如果 A == nil ,说明 A 中节点不足以构成子结构 B ，返回 false
        return false
    }
    if A.Val != B.Val { //  A.Val != B.Val，不满足节点值相等条件，返回 false
        return false
    }
    return helper(A.Left, B.Left) && helper(A.Right, B.Right)
}

331. 验证二叉树的前序序列化

序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。

1
2
3
4
5
6
7
     _9_
    /   \
   3     2
  / \   / \
 4   1  #  6
/ \ / \   / \
# # # #   # #

例如，上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一个空节点。

给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。

每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的'#'。

你可以认为输入格式总是有效的，例如它永远不会包含两个连续的逗号，比如 "1,,3" 。

示例 1:

1
2
输入: "9,3,4,#,#,1,#,#,2,#,6,#,#"
输出: true

示例 2:

1
2
输入: "1,#"
输出: false

示例 3:

1
2
输入: "9,#,#,1"
输出: false

解题思路：

  我们可以定义一个概念，叫做槽位。一个槽位可以被看作「当前二叉树中正在等待被节点填充」的那些位置。

二叉树的建立也伴随着槽位数量的变化。每当遇到一个节点时：

  • 如果遇到了空节点，则要消耗一个槽位；
  • 如果遇到了非空节点，则除了消耗一个槽位外，还要再补充两个槽位。

此外，还需要将根节点作为特殊情况处理。

  我们使用栈来维护槽位的变化。栈中的每个元素，代表了对应节点处剩余槽位的数量，而栈顶元素就对应着下一步可用的槽位数量。当遇到空节点时，仅将栈顶元素减 1；当遇到非空节点时，将栈顶元素减 1 后，再向栈中压入一个 2。无论何时，如果栈顶元素变为 0，就立刻将栈顶弹出。遍历结束后，若栈为空，说明没有待填充的槽位，因此是一个合法序列；否则若栈不为空，则序列不合法。此外，在遍历的过程中，若槽位数量不足，则序列不合法。

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
func isValidSerialization(preorder string) bool {
    n := len(preorder)
    stk := []int{1} // 初始化一个槽位给根节点

    for i:=0; i<n; {
        if len(stk) == 0 { // 已经没有足够的槽位，但序列还未结束，说明序列不合法
            return false
        }

        if preorder[i] == ',' {
            i++
        } else if preorder[i] == '#' { // 出现空节点
            stk[len(stk)-1]--  // 消耗栈顶一个槽位
            if stk[len(stk)-1] == 0 { // 若栈顶槽位置零，则出栈
                stk = stk[:len(stk)-1]
            }
            i++
        } else {
            for i<n && preorder[i] != ',' { // 读取数字
                i++
            }
            stk[len(stk)-1]-- // 消耗栈顶一个槽位
            if stk[len(stk)-1] == 0 { // 若栈顶槽位置零，则出栈
                stk = stk[:len(stk)-1]
            }
            stk = append(stk,2) // 每出现一个新非空节点，入栈一个有2个槽位的元素
        }
    }
    return len(stk) == 0  // 遍历结束后，没有空槽位说明序列合法
}

3.设置全局变量实时记录并更新递归过程中的极值

  此类题目最终的输出是一个单一的值，我们需要维护一个全局变量来记录这一个单一值，并在递归遍历二叉树的过程中实时地更新这个值。用于递归的辅助函数的返回结果不必与这个值直接联系，要着眼于构建二叉树的节点间的关系。

124. 二叉树中的最大路径和

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

路径和是路径中各节点值的总和。

给你一个二叉树的根节点 root ，返回其 最大路径和 。

示例 1：

avatar

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

示例 2：

avatar

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

提示：

  • 树中节点数目范围是 [1, 3 * 104]
  • -1000 <= Node.val <= 1000

解题思路：

  1. 首先考虑辅助函数的功能。考虑实现一个简化的函数 maxGain(node)，该函数计算二叉树中的一个节点的最大贡献值，具体而言，就是在以该节点为根节点的子树中寻找以该节点为起点的一条路径，使得该路径上的节点值之和最大。具体而言，该函数的计算如下:
  • 空节点的最大贡献值等于 0。
  • 非空节点的最大贡献值等于节点值与其子节点中的最大贡献值之和（对于叶节点而言，最大贡献值等于节点值）。

例如，考虑如下二叉树。

1
2
3
4
5
 -10
 / \
9  20
  /  \
 15   7

  叶节点 9、15、7 的最大贡献值分别为 9、15、7。得到叶节点的最大贡献值之后，再计算非叶节点的最大贡献值。节点 20 的最大贡献值等于 20+max⁡(15,7)=35。节点 −10 的最大贡献值等于 −10+max⁡(9,35)=25。上述计算过程是递归的过程，因此，对根节点调用函数 maxGain，即可得到每个节点的最大贡献值。

  根据函数 maxGain 得到每个节点的最大贡献值之后，如何得到二叉树的最大路径和？对于二叉树中的一个节点，该节点的最大路径和取决于该节点的值与该节点的左右子节点的最大贡献值，如果子节点的最大贡献值为正，则计入该节点的最大路径和，否则不计入该节点的最大路径和。维护一个全局变量 maxSum 存储最大路径和，在递归过程中更新 maxSum 的值，最后得到的 maxSum 的值即为二叉树中的最大路径和。

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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func  maxPathSum(root *TreeNode) int {
  	maxSum := math.MinInt32  // 设置全局变量用于实时比较及更新每个节点作为根节点时的最大路径
  	
  	var gotMax func(root *TreeNode) int
  	gotMax = func(root *TreeNode) int {
      	if root == nil {  // 递归出口
        		return 0
      	}
      	
      	left := max(gotMax(root.Left),0)  // 当前节点的左子树的最大贡献值（如果小于0则置0）
      	right := max(gotMax(root.Right),0)  // 当前节点右子树的最大贡献值（如果小于0则置0）
      	now := root.Val + left + right  // 记录以当前节点作为根节点的最大路径
      	maxSum = max(maxSum,now) // 更新最大值
      
      	return root.Val+max(left,right)  // 返回当前节点的最大贡献值
  	}
		
  	gotMax(root)
  	return maxSum
}

func max(a,b int) int {
  	if a>=b {
    	return a
  	}
  	return b
}

543. 二叉树的直径

给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。

示例 :
给定二叉树

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

返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。

注意：两结点之间的路径长度是以它们之间边的数目表示。

解题思路：

  任意一条路径均可以被看作由某个节点为起点，从其左儿子和右儿子向下遍历的路径拼接得到。假设我们知道对于某节点的左儿子向下遍历经过最多的节点数 $L$ （即以左儿子为根的子树的深度） 和其右儿子向下遍历经过最多的节点数 $R$ （即以右儿子为根的子树的深度），那么以该节点为起点的路径经过节点数的最大值即为 $L+R+1$ 。

  最后的算法流程为：我们定义一个递归函数 depth(node) 计算 $d_{node}$，函数返回该节点为根的子树的深度。先递归调用左儿子和右儿子求得它们为根的子树的深度 $L$ 和 $R$ ，则该节点为根的子树的深度即为 $\max (L, R)+1$, 该节点的 $d_{node}$ 值为$L+R+1$。递归搜索每个节点并设一个全局变量 maxSum 来记录并随时更新最大直径。

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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

var maxSum int  // 全局变量用于记录最大直径
func diameterOfBinaryTree(root *TreeNode) int {
  	naxSum = 0
  	if root == nil {
    		return 0
  	}
  	depth(root)
  	return maxSum
}

func depth(root *TreeNode) int { // 该辅助函数用于返回每个节点的深度
  	if root == nil {
    		return 0
  	}
  	
  	left := depth(root.Left)
  	right := depth(root.Right)
  
  	if left+right+1 > maxSum { // 更新最大直径的值
    		maxSum = left + right + 1
  	}
  
  	return 1+max(left,right)
}

func max(a,b int) int {
  	if a > b {
    	return a
  	}
  	return b
}

4.结果要求返回数组

  由于递归算法本身在递归的过程中没法返回数组，所以可以通过设置全局变量的方式，在递归过程中动态的更新数组。

113. 路径总和 II

给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。

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

示例 1：

avatar

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

示例 2：

avatar

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

示例 3：

1
2
输入：root = [1,2], targetSum = 0
输出：[]

提示：

1
2
3
树中节点总数在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000
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.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func pathSym(root *TreeNode, targetSum int) [][]int {
  	ret := make([][]int,0)
  	path := make([]int,0)
  	
  	if root == nil {
    	return nil
  	}
  
  	helper(root,targetSum,&ret,path)
  	return ret
}


func helper(root *TreeNode, targetSum int, ret *[][]int, path []int) {
  
  	if root == nil {
    	return
  	}
  
  	sum := targetSum - root.Val
  	path = append(path,root.Val)
  	if root.Left == nil && root.Right == nil && sum == 0 {
      // / 创建一个辅助数组用于保存path的当前值，否则path会随递归操作而回溯
    	dst := make([]int,len(path))  
    	copy(dst,path)
    	*ret = append(*ret, dst)
    	return
  	}
  
  	helper(root.Left, targetSum-root.Val, ret, path)
  	helper(root.Right, targetSum-root.Val, ret, path)
}

129. 求根节点到叶节点数字之和

给你一个二叉树的根节点 root ，树中每个节点都存放有一个 0 到 9 之间的数字。

每条从根节点到叶节点的路径都代表一个数字：

  • 例如，从根节点到叶节点的路径 1 -> 2 -> 3 表示数字 123 。

计算从根节点到叶节点生成的 所有数字之和 。

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

示例 1：

avatar

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

示例 2：

avatar

1
2
3
4
5
6
7
输入：root = [4,9,0,5,1]
输出：1026
解释：
从根到叶子节点路径 4->9->5 代表数字 495
从根到叶子节点路径 4->9->1 代表数字 491
从根到叶子节点路径 4->0 代表数字 40
因此，数字总和 = 495 + 491 + 40 = 1026

提示：

  • 树中节点的数目在范围 [1, 1000] 内
  • 0 <= Node.val <= 9
  • 树的深度不超过 10

解题思路：

  深度优先搜索是很直观的做法。从根节点开始，遍历每个节点，如果遇到叶子节点，则将叶子节点对应的数字加到数字之和。如果当前节点不是叶子节点，则计算其子节点对应的数字，然后对子节点递归遍历。

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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sumNumbers(root *TreeNode) int {
    nodeArray := make([]int,0)
    path := make([]int,0)
    helper(root, &nodeArray, path)

    ret := 0
    for _, value := range nodeArray {
        ret += value
    }
    return ret
}

func helper(root *TreeNode, array *[]int, path []int) {
    if root == nil {
        return
    }

    path = append(path, root.Val)
    if root.Left == nil && root.Right == nil {
        node := 0
        for i:=len(path)-1; i>=0; i-- {
            node += path[i]* int(math.Pow10(len(path)-i-1))
        }
        *array = append(*array,node)

    }
    helper(root.Left, array, path)
    helper(root.Right, array, path)
}

257. 二叉树的所有路径

给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。

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

示例 1：

avatar

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

示例 2：

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

提示：

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

解题思路：

  • 当遍历到根节点时，将根节点的值转化成字符串后贴到路径串中，并将该条路径存入ret中；
  • 当不是根节点时，将根节点的值转化成字符串后贴到路径串中，并在其后加入符号->。
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.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func binaryTreePaths(root *TreeNode) []string {
    ret := make([]string,0)
    path := ""
    helper(root,&ret,path)
    return ret
}

func helper(root *TreeNode, ret *[]string, path string) {
    if root == nil { // 递归出口
        return
    }

    if root.Left == nil && root.Right == nil { // 当是根节点时，该条路径遍历结束，存入ret
        path = path + strconv.Itoa(root.Val)
        dst := ""
        dst = path        
        *ret = append(*ret, dst)
    } else {
        path = path + strconv.Itoa(root.Val) + "->"
    }

    helper(root.Left, ret, path)
    helper(root.Right, ret, path)
}

863. 二叉树中所有距离为 K 的结点

给定一个二叉树（具有根结点 root）， 一个目标结点 target ，和一个整数值 K 。

返回到目标结点 target 距离为 K 的所有结点的值的列表。 答案可以以任何顺序返回。

示例 1：

1
2
3
4
5
6
7
输入：root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2
输出：[7,4,1]
解释：
所求结点为与目标结点（值为 5）距离为 2 的结点，值分别为 7，4，以及 1

注意，输入的 "root" 和 "target" 实际上是树上的结点。
上面的输入仅仅是对这些对象进行了序列化描述。

avatar

提示：

  • 给定的树是非空的。
  • 树上的每个结点都具有唯一的值 0 <= node.val <= 500 。
  • 目标结点 target 是树上的结点。
  • 0 <= K <= 1000.

解题思路：

若将 target 当作树的根结点，我们就能从 target 出发，使用深度优先搜索去寻找与 target 距离为 k 的所有结点，即深度为 k 的所有结点。

由于输入的二叉树没有记录父结点，为此，我们从根结点 root 出发，使用深度优先搜索遍历整棵树，同时用一个哈希表记录每个结点的父结点。

然后从 target 出发，使用深度优先搜索遍历整棵树，除了搜索左右儿子外，还可以顺着父结点向上搜索。

代码实现时，由于每个结点值都是唯一的，哈希表的键可以用结点值代替。此外，为避免在深度优先搜索时重复访问结点，递归时额外传入来源结点 from，在递归前比较目标结点是否与来源结点相同，不同的情况下才进行递归。通过标记源结点，如图结点2遍历到7时，由于存在7->2的边，可能会重复遍历。由于存在我们预先标记的源节点只有当cur != from的时候才能继续遍历。

avatar

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
44
45
46
47
48
49
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func distanceK(root *TreeNode, target *TreeNode, k int) []int {
    m := make(map[int]*TreeNode,0) // 初始化map用于存储父节点
    var parent func(*TreeNode) 
    parent = func(root *TreeNode) { // 递归存储每个节点的父节点
        if root == nil {
            return
        }
        if root.Left != nil {
            m[root.Left.Val] = root
            parent(root.Left)
        }
        if root.Right != nil {
            m[root.Right.Val] = root
            parent(root.Right)
        }
    }
    parent(root)

    ret := []int{}
    var disK func(*TreeNode,*TreeNode,int) // // 从 target 出发 DFS，寻找所有深度为 k 的结点
    disK = func(root *TreeNode, from *TreeNode, depth int) {
        if root == nil {
            return
        }
        if depth == k { // 距离等于k，存入ret并剪枝
            ret = append(ret, root.Val)
            return
        }
        if root.Left != from { // 左节点
            disK(root.Left, root, depth+1)
        }
        if root.Right != from { // 右节点
            disK(root.Right, root, depth+1)
        }
        if m[root.Val] != from { // 父节点
            disK(m[root.Val], root, depth+1)
        }
    }
    disK(target,nil,0)
    return ret
}

二叉搜索树(BST)

二叉搜索树(BST)的特性

  1. 对于 BST 的每一个节点 node，左子树节点的值都比 node 的值要小，右子树节点的值都比 node 的值大。
  2. 对于 BST 的每一个节点 node，它的左侧子树和右侧子树都是 BST。
  3. 从做算法题的角度来看 BST，除了它的定义，还有一个重要的性质：BST 的中序遍历结果是有序的（升序）。

BST必知必会题

1. 判断BST的合法性(98. 验证二叉搜索树)

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

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

示例1:

1
2
3
4
5
输入:
    2
   / \
  1   3
输出: true

示例 2:

1
2
3
4
5
6
7
8
9
输入:
    5
   / \
  1   4
     / \
    3   6
输出: false
解释: 输入为: [5,1,4,null,null,3,6]。
     根节点的值为 5 ，但是其右子节点值为 4 。

解题思路：

对于每一个节点 **root，代码值检查了它的左右孩子节点是否符合左小右大的原则；但是根据 BST 的定义，root**的整个左子树都要小于 **root.val**，整个右子树都要大于 **root.val**。

问题是，对于某一个节点 root，他只能管得了自己的左右子节点，怎么把 root 的约束传递给左右子树呢？我们通过使用辅助函数，增加函数参数列表，在参数中携带额外信息，将这种约束传递给子树的所有节点，这也是二叉树算法的一个小技巧吧。

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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

func isValidBST(root *TreeNode) boll {
  	return helper(root, nil, nil)
}

func helper(root *TreeNode, max *TreeNode, min *TreeNode) bool {
  	if root == nil {
    		return true
  	}
  
  	if min != nil && root.Val <= min.Val {
    		return false
  	}
  	if max != nil && root.Val >= max.Val {
    		return false
  	}
  
  	return helper(root.Left, root, min) && helper(root.Right, max, root)
}

2. 在BST中搜索一个数

  直接利用BST的性质前序遍历二叉搜索树，当当前节点值等于target，直接返回true，如果当前节点值大于target，则在其左子树中寻找；如果小于target，在其右子树中寻找。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func isInBST(root *TreeNode, target int) bool {
  	if root == nil {
    		return false
  	}
  	if root.Val == target {
    		return true
  	}
  	if root.Val > target {
    		return isInBST(root.Left, target)
  	}
  	if root.Val < target {
    		return isInBST(root.Right, target)
  	}
}

3. 在BST中插入一个数

  涉及到“改”这一操作，就要返回TreeNode类型了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func insertIntoBST(root *TreeNode, val int) *TreeNode {
  	if root == nil {  // 找到空位置插入新节点
    		node := &TreeNode{val,nil,nil}
    		return node
  	}
  
  	if root.Val < val { // 在右子树的叶节点中插入val
    		root.Right = insertIntoBST(root.Right,val)
  	}
  
  	if root.Val > val { // 在左子树的叶节点中插入val
    		root.Left = insertIntoBST(root.Left,val)
  	}
}

4. 在BST中删除一个数

  这个问题稍微复杂，跟插入操作类似，先「找」再「改」。找到目标节点了，比方说是节点 A，如何删除这个节点，这是难点。因为删除节点的同时不能破坏 BST 的性质。有三种情况，用图片来说明。

  • 情况1: A 恰好是末端节点，两个子节点都为空，那么可以直接将其删除。

avatar

  • 情况2: A 只有一个非空子节点，那么它要让这个孩子接替自己的位置。

avatar

  • 情况 3：A 有两个子节点，麻烦了，为了不破坏 BST 的性质，A 必须找到左子树中最大的那个节点，或者右子树中最小的那个节点来接替自己。我们以第二种方式讲解。

avatar

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
func deleteNode(root *TreeNode, key int) *TreeNode {
  	if root == nil {
    		return nil
  	}
  
  	if root.Val == key {
    		// 下面两个if把case1和case2都处理了
    		if root.Left == nil {
      			return root.Right
    		}
    		if root.Right == nil {
      			return root.Left
    		}
    
    		// case3
    		minNode := getNode(root.Right)
      	root.Val = minNode.Val // 将当前根节点的值用右子树最小值(一定是叶节点)替换
    		root.Right = deletNode(root.Right, minNode.Val) // 删除掉被替换后的叶节点
  	} else if root.Val > key {
    		root.Left = deleteNode(root.Left,key)
  	} else if root.Val < key {
    		root.Right = deleteNode(root.Left,key)
  	}
  	return root
}

func getMin(root *TreeNode) *TreeNode {
  	for node.Left != nil {
    		root = root.Left
  	}
  	return root
}

BST高频题

96. 不同的二叉搜索树

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

示例 1：

avatar

1
2
输入：n = 3
输出：5

示例 2：

1
2
输入：n = 1
输出：1

提示：

  • 1 <= n <= 19

解题思路：(搬运自不同的二叉搜索树)

  给定一个有序序列 $1⋯n$，为了构建出一棵二叉搜索树，我们可以遍历每个数字 $i$，将该数字作为树根，将 $1⋯(i−1)$ 序列作为左子树，将 $(i+1)⋯n$ 序列作为右子树。接着我们可以按照同样的方式递归构建左子树和右子树。

  在上述构建的过程中，由于根的值不同，因此我们能保证每棵二叉搜索树是唯一的。由此可见，原问题可以分解成规模较小的两个子问题，且子问题的解可以复用。因此，我们可以想到使用动态规划来求解本题。

  题目要求是计算不同二叉搜索树的个数。为此，我们可以定义两个函数：

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

  可见，$G(n)$ 是我们求解需要的函数。稍后我们将看到，$G(n)$ 可以从 $F(i,n)$ 得到，而 $F(i,n)$ 又会递归地依赖于 $G(n)$。

  首先，根据上一节中的思路，不同的二叉搜索树的总数 $G(n)$，是对遍历所有 $(1≤i≤n)$ 的 $F(i,n)$ 之和。换言之：

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

  对于边界情况，当序列长度为 11（只有根）或为 00（空树）时，只有一种情况，即：

$G(0)=1, \quad G(1)=1$

  给定序列 $1⋯n$，我们选择数字 $i$ 作为根，则根为 $i$ 的所有二叉搜索树的集合是左子树集合和右子树集合的笛卡尔积，对于笛卡尔积中的每个元素，加上根节点之后形成完整的二叉搜索树，如下图所示：

avatar

  举例而言，创建以 3 为根、长度为 7 的不同二叉搜索树，整个序列是 $[1,2,3,4,5,6,7]$，我们需要从左子序列 $[1,2]$ 构建左子树，从右子序列 $[4,5,6,7]$ 构建右子树，然后将它们组合（即笛卡尔积）。对于这个例子，不同二叉搜索树的个数为 $F(3,7)$。我们将 $[1,2]$ 构建不同左子树的数量表示为 $G(2)$, 从 $[4,5,6,7]$ 构建不同右子树的数量表示为 $G(4)$，注意到 $G(n)$ 和序列的内容无关，只和序列的长度有关。于是，$F(3,7)=G(2)⋅G(4)$。 因此，我们可以得到以下公式：

$F(i, n)=G(i-1) \cdot G(n-i)$

将公式结合，可以得到 $G(n)$ 的递归表达式：

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

至此，我们从小到大计算 $G$ 函数即可，因为 $G(n)$ 的值依赖于 $G(0)⋯G(n−1)$。

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
func numTrees(n int) int {
  	m := make([][]int,n)  // 初始化一个二维数组充当记事本
  	for i:=0; i<n; i++ {
    		m[i] = make([]int,n)
  	}
  	return count(1,n,m)
}

func count(l int, r int, m [][]int) int {
  	if l > r {
    		return 1
  	}
  
  	if m[l-1][r-1] != 0 {
    		return m[l-1][r-1]
  	}
  
  	for i:=l; i<=r; i++ {
    		left := count(l,i-1,m)
    		right := count(i+1,r,m)
				ret += left*right  // 笛卡尔乘积
  	}
  
  	m[l-1][r-1] = ret
  	return ret
}

95. 不同的二叉搜索树 II

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

示例 1：

avatar

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

示例 2：

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

提示：

  • 1 <= n <= 8

解题思路：

二叉搜索树关键的性质是根节点的值大于左子树所有节点的值，小于右子树所有节点的值，且左子树和右子树也同样为二叉搜索树。因此在生成所有可行的二叉搜索树的时候，假设当前序列长度为 n，如果我们枚举根节点的值为 i，那么根据二叉搜索树的性质我们可以知道左子树的节点值的集合为 [1…i−1]，右子树的节点值的集合为 [i+1…n]。而左子树和右子树的生成相较于原问题是一个序列长度缩小的子问题，因此我们可以想到用回溯的方法来解决这道题目。

我们定义 generateTrees(start, end) 函数表示当前值的集合为 [start,end]，返回序列 [start,end] 生成的所有可行的二叉搜索树。按照上文的思路，我们考虑枚举 [start,end] 中的值 i 为当前二叉搜索树的根，那么序列划分为了 [start,i−1] 和 [i+1,end] 两部分。我们递归调用这两部分，即 generateTrees(start, i - 1) 和 generateTrees(i + 1, end)，获得所有可行的左子树和可行的右子树，那么最后一步我们只要从可行左子树集合中选一棵，再从可行右子树集合中选一棵拼接到根节点上，并将生成的二叉搜索树放入答案数组即可。

递归的入口即为 generateTrees(1, n)，出口为当 start>end 的时候，当前二叉搜索树为空，返回空节点即可。

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
/**
 * 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 getBST(1,n)
}

func getBST(l int, r int) []*TreeNode {
  	if l > r {
      	return []*TreeNode{nil} 
  	}
  	
  	ret := make([]*TrrNode,0)
  	// 枚举可行根节点
  	for i:=l; i<=r; i++ {
      	// 获得所有可行的左子树集合
    		leftTree := getBST(l,i-1)
      // 获得所有可行的右子树集合
    		tightTree := getBST(i+1,r)
    		// 从左子树集合中选出一棵左子树，从右子树集合中选出一棵右子树，拼接到根节点上
    		for _,left := range leftTree {
      			for _,right := range rightTree {
        				root := &TreeNode{i,nil,nil}
        				root.Left = left
        				root.Right = right
        				ret = append(ret,root)
      			}
    		}
  	}
  	return ret
}

99. 恢复二叉搜索树

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

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

示例 1：

avatar

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

示例 2：

avatar

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

提示：

  • 树上节点的数目在范围 [2, 1000] 内
  • -231 <= Node.val <= 231 - 1

解题思路：

  我们需要考虑两个节点被错误地交换后对原二叉搜索树造成了什么影响。对于二叉搜索树，我们知道如果对其进行中序遍历，得到的值序列是递增有序的，而如果我们错误地交换了两个节点，等价于在这个值序列中交换了两个值，破坏了值序列的递增性。

  我们来看下如果在一个递增的序列中交换两个值会造成什么影响。假设有一个递增序列 a=[1,2,3,4,5,6,7]。如果我们交换两个不相邻的数字，例如 2 和 6，原序列变成了 a=[1,6,3,4,5,2,7]，那么显然序列中有两个位置不满足 $a_{i}$<$a_{i+1}$，在这个序列中体现为6>3，5>2，因此只要我们找到这两个位置，即可找到被错误交换的两个节点。如果我们交换两个相邻的数字，例如 2 和 3，此时交换后的序列只有一个位置不满足 $a_{i}$<$a_{i+1}$。因此整个值序列中不满足条件的位置或者有两个，或者有一个。

  至此，解题方法已经呼之欲出了：

  1. 找到二叉搜索树中序遍历得到值序列的不满足条件的位置。
  2. 如果有两个，我们记为 i 和 j（i<j 且 $a_{i}$>$a_{i+1}$ && $a_{j}$>$a_{j+1}$，那么对应被错误交换的节点即为$a_{i}$对应的节点和$a_{i+1}$对应的节点，我们分别记为 x 和 y。
  3. 如果有一个，我们记为 i，那么对应被错误交换的节点即为$a_{i}$对应的节点和$a_{i+1}$对应的节点，我们分别记为 x 和 y。
  4. 交换 x 和 y 两个节点即可。

  实现部分，本方法开辟一个新数组 nums 来记录中序遍历得到的值序列，然后线性遍历找到两个位置 i 和 j，并重新遍历原二叉搜索树修改对应节点的值完成修复，具体实现可以看下面的代码。

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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func recoverTree(root *TreeNode)  {

    nums := make([]int,0)
    var inorder func(*TreeNode) // 中序遍历保存序列
    inorder = func(root *TreeNode) {
        if root == nil {
            return
        }
        inorder(root.Left)
        nums = append(nums,root.Val)
        inorder(root.Right)
    }
    inorder(root)
    A, B := helper(nums)
    fmt.Println(A,B)
    recover(A, B, 2, root)
}

func helper(nums []int) (int,int) { // 返回两个顺序错误的节点的值
    x,y := math.MinInt32, -1
    for i:=0; i<len(nums)-1; i++ {
        if nums[i+1] < nums[i] {
            y = nums[i+1]
            if x == math.MinInt32 {
                x = nums[i]
            } else {
                break
            }
        }
    }
    return x,y
} 

func recover(A int, B int, count int, root *TreeNode) { // 遍历二叉树，改变这两个节点值
    if root == nil {
        return
    }
    if root.Val == A || root.Val == B {
        if root.Val == A {
            root.Val = B 
        } else {
            root.Val = A
        }
        count-- // 用于计数，当两个节点都被改变后，直接跳出递的过程，剪枝
        if count == 0 {
            return
        }
    }

    recover(A, B, count, root.Left)
    recover(A, B, count, root.Right)
}
  • Post title：递归算法解决二叉树问题
  • Post author：洪笳淏
  • Create time：2021-08-18 18:00:00
  • Post link：https://jiahaohong1997.github.io/2021/08/18/递归算法解决二叉树问题/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.
 Comments