二叉树-解题思路

二叉树的问题主要涉及到两大类思路，遍历和递归。

二叉树的前提下，“递归”不再是以 for 循环的情况出现¹，而是回归到其本质：每个节点都看一眼，并且不断维护和更新外部变量。遍历有点类似一个指针在树上游走

Note

二叉树的递归和遍历，遍历和递归都是使用的同一套代码模板，也都是不断调用同一个函数来实现，但是思想上是不一样。 目前我的感觉是这样：遍历没有返回值，需要维护外部变量，比如定义一个全局的结果变量，遍历的过程中直接操作这个全局的结果变量；而递归是有返回值的，我们需要做的是分解问题，重复利用起每个子问题的返回值。

应用递归和遍历，对应两种不同的思路。

1. 能不能我把每个节点看一遍，就能得到答案。 → 遍历
2. 问题能不能分解成左右子树的子问题？ → 递归

在每个思路下，我们需要想的是下面的问题：

1. 每个节点上，我应该干什么？添加怎样的代码？
2. 我应该在前序位置操作，还是应该在后序位置操作² ?

   Note

   在前序位置操作的，一般对于操作位置不敏感，即放在哪儿都行。 在后序位置操作的，是需要得知左右子树的信息之后才能进行的操作。

递归解决二叉树问题的步骤

• 并不是所有的二叉树的问题都可以递归解决
• 递归解决的二叉树问题一定可以分解成最优子结构的子问题

按照如下步骤考虑：

1. 分解成子问题，每个树，我需要知道子树的什么信息就能解决当前的子问题了？

   注意递归返回的信息不管左右树都应该是一样，如果需要的信息左右树的不一样，就全都返回来（先当成黑盒），在取所需

2. 根据拿到的信息，在后序的位置解决这个子问题

   可能需要很多判断语句

3. 想一想 base case 的返回值应该是什么。如果不知道base case返回什么，就可以试试返回空，然后在后序的位置拿到信息后判断一下。
4. 制作当前节点的返回值，需要和1中是一样的
5. 递归调用就行了

例子 1

问题：98. 验证二叉搜索树 - 力扣（LeetCode）

思考流程

1. 分解子问题：一个树是二叉搜索树，那么其每个节点一定满足：①左子树是二叉搜索树 ②右子树是二叉搜索树 ③左子树的最大值小于当前节点值 ④右子树的最小值大于当前节点值。

   可以看到，对于左右子树的信息，我们需要的是不一样的（左子树要最大值，右子树要最小值），那么干脆最大最小值都返回来。 综上，我们需要左右子树的信息是：是不是二叉搜索树、最大值、最小值

2. 根据拿到的信息判断当前节点为根节点的树是不是二叉搜索树
3. 思考base case
4. 制作当前节点的返回值
5. 递归开始

代码

# 1. 返回的结构体，返回三个信息
class Info():
    def __init__(self, isBST, mi, ma):
        self.isBST = isBST
        self.min = mi
        self.max = ma
 
class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        def recur(node):
	        # 3. base case
            if node == None:
                # 这里不能返回Info(True, -float('inf'), float('inf'))，不然出错
                return Info(True, float('inf'), -float('inf'))
 
            left = recur(node.left)
            right = recur(node.right)
            #2. 解决当前子问题
            isBST = False
            if (node.val > left.max) and (node.val < right.min) and (left.isBST) and (right.isBST):
                isBST = True
            #4. 获取当前节点返回值
            mi = min(node.val, left.min, right.min)
            ma = max(node.val, left.max, right.max)
            return Info(isBST, mi, ma)    
        # 5. 递归开始
        out = recur(root)
        return out.isBST

Tips

在应用递归的时候，如果需要结合回溯思想，在外部维护一个辅助变量，要记得在进入和离开一个节点的时候，及时的添加和弹出相关的内容，相关问题可以看看路径总和II中对于path的维护

Footnotes

1. 譬如在链表中对链表遍历，就可以使用 for ↩

2. 在中序位置操作的目前还没遇到 ↩