算法刷题总结 (十一) 二叉树

算法总结11 二叉树

一、二叉树的概念

二叉树作为一个基础的数据结构，遍历算法作为一个基础的算法，两者结合当然是经典的组合了。很多题目都会有他的身影，有直接问二叉树的遍历的，有间接问的。比如要你找到树中满足条件的节点，就是间接考察树的遍历，因为你要找到树中满足条件的点，就需要进行遍历。你如果掌握了二叉树的遍历，那么也许其他复杂的树对于你来说也并不遥远了。

1.1、什么是二叉树？

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分。

二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个节点 。

总之：二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树

请添加图片描述


1.2、二叉树的常见类型


1.2.1、无数值

（1）、满二叉树

满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。

如图所示：
在这里插入图片描述
这棵二叉树为满二叉树，也可以说深度为 k k k，有 2 k − 1 2^k-1 2k−1个节点的二叉树。


（2）、完全二叉树

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h h h 层，则该层包含 1 − 2 ( h − 1 ) 1- 2^{(h-1)} 1−2(h−1) 个节点。
在这里插入图片描述
优先级队列其实是一个堆，堆就是一棵完全二叉树，同时保证父子节点的顺序关系。


1.2.2、有数值

（3）、二叉搜索树

前面介绍的树，都没有数值的，而二叉搜索树是有数值的了，二叉搜索树是一个有序树。

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树
下面这两棵树都是搜索树:
在这里插入图片描述

（4）、平衡二叉搜索树

平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

如图：
在这里插入图片描述
最后一棵 不是平衡二叉树，因为它的左右两个子树的高度差的绝对值超过了1。


1.3、二叉树的存储方式

方式一方式二
链式存储顺序存储
使用指针，通过指针把分布在各个地址的节点串联一起使用数组，元素在内存是连续分布的

（1）、链式存储方式

在这里插入图片描述

class TreeNode:
     def __init__(self, val=0, left=None, right=None):
         self.val = val
         self.left = left
         self.right = right

二叉树的定义 和链表是差不多的，相对于链表 ，二叉树的节点里多了一个指针， 有两个指针，指向左右孩子。


（2）、顺序存储方式

在这里插入图片描述
用数组来存储二叉树如何遍历的呢？

如果父节点的数组下标是 i，那么它的左孩子就是 i × 2 + 1 i \times 2 + 1 i×2+1，右孩子就是 i × 2 + 2 i \times 2 + 2 i×2+2。

但是用链式表示的二叉树，更有利于我们理解，所以一般我们都是用链式存储二叉树。


1.4、二叉树的遍历方式

二叉树主要有两种遍历方式：

遍历方式深度优先遍历广度优先遍历
解释先往深走，遇到叶子节点再往回走一层一层的去便利
实现方法前序遍历（递归法，迭代法）、中序遍历（递归法，迭代法）、后序遍历（递归法，迭代法）层次遍历（迭代法）

在深度优先遍历中：有三个顺序，前中后序遍历，这三个顺序很容易搞混，这里有一个技巧去辨识：这里前中后，其实指的就是中间根节点的遍历顺序，只要记住 前中后序指的就是中间节点的位置就可以了。

看如下中间节点的顺序，就可以发现，中间节点的顺序就是所谓的遍历方式：

前序遍历：中左右
中序遍历：左中右
后序遍历：左右中

可以对着如下图，看看自己理解的前后中序有没有问题：
在这里插入图片描述
最后再说一说二叉树中深度优先和广度优先遍历实现方式，我们做二叉树相关题目，经常会使用递归的方式来实现深度优先遍历，也就是实现前中后序遍历，使用递归是比较方便的。

之前我们讲栈与队列的时候，就说过栈其实就是递归的一种实现结构，也就说前中后序遍历的逻辑其实都是可以借助栈使用非递归的方式来实现的。

而广度优先遍历的实现一般使用队列来实现，这也是队列先进先出的特点所决定的，因为需要先进先出的结构，才能一层一层的来遍历二叉树。

这里其实我们又了解了栈与队列的一个应用场景了。


1.5、二叉树的递归遍历

每次写递归，都按照这三要素来写：

三要素过程
1. 确定递归函数的参数和返回值确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数， 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
2. 确定终止条件写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
3. 确定单层递归的逻辑确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

（1）、前序遍历

仅以前序遍历为例：

1.确定递归函数的参数和返回值：因为要打印出前序遍历节点的数值，所以参数里需要传入result来放节点的数值，除了这一点就不需要再处理什么数据了也不需要有返回值，所以递归函数返回类型就是空，代码如下：

# root为遍历的节点，result为存储节点的list
result = []

def traversal(root: TreeNode):

2.确定终止条件：在递归的过程中，如何算是递归结束了呢，当然是当前遍历的节点是空了，那么本层递归就要结束了，所以如果当前遍历的这个节点是空，就直接return，代码如下：

if root == None:
	return

3.确定单层递归的逻辑：前序遍历是中左右的循序，所以在单层递归的逻辑，是要先取中节点的数值，代码如下：

result.append(root.val);    // 中
traversal(cur.left, result);  // 左
traversal(cur.right, result); // 右

单层递归的逻辑就是按照中左右的顺序来处理的，这样二叉树的前序遍历，基本就写完了，再看一下完整代码：

# 前序遍历-递归-LC144_二叉树的前序遍历
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        # 保存结果
        result = []
        
        def traversal(root: TreeNode):
            if root == None:
                return
            result.append(root.val) # 前序
            traversal(root.left)    # 左
            traversal(root.right)   # 右

        traversal(root)
        return result

（2）、中序遍历

举一反三，只需要调换一下顺序即可：

# 中序遍历-递归-LC94_二叉树的中序遍历
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        result = []

        def traversal(root: TreeNode):
            if root == None:
                return
            traversal(root.left)    # 左
            result.append(root.val) # 中序
            traversal(root.right)   # 右

        traversal(root)
        return result

（3）、后序遍历

举一反三，只需要调换一下顺序即可：

# 后序遍历-递归-LC145_二叉树的后序遍历
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        result = []

        def traversal(root: TreeNode):
            if root == None:
                return
            traversal(root.left)    # 左
            traversal(root.right)   # 右
            result.append(root.val) # 后序

        traversal(root)
        return result

链表写法：

nums ='1 2 3 4 5 6 7'
nums = list(map(int, nums.split()))
n = len(nums)
res = []

def back(root):
    if root>=n:
        return None
    a = back(root*2+1)
    b = back(root*2+2)

    res.append(nums[root])
    
back(0)
res

1.6、二叉树的迭代遍历

为什么可以用迭代法（非递归的方式）来实现二叉树的前后中序遍历呢？

递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。

此时应该明白用栈也可以是实现二叉树的前后中序遍历了。

（1）、前序遍历

我们先看一下前序遍历。

前序遍历是中左右，每次先处理的是中间节点，那么先将根节点放入栈中，然后将右孩子加入栈，再加入左孩子。

为什么要先加入 右孩子，再加入左孩子呢？ 因为这样出栈的时候才是中左右的顺序。

动画如下：
请添加图片描述

# 前序遍历-迭代-LC144_二叉树的前序遍历
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        # 根结点为空则返回空列表
        if not root:
            return []
        stack = [root]
        result = []
        while stack:
            node = stack.pop()
            # 中结点先处理
            result.append(node.val)
            # 右孩子先入栈
            if node.right:
                stack.append(node.right)
            # 左孩子后入栈
            if node.left:
                stack.append(node.left)
        return result

此时会发现貌似使用迭代法写出前序遍历并不难，确实不难。

此时是不是想改一点前序遍历代码顺序就把中序遍历搞出来了？

其实还真不行！

但接下来，再用迭代法写中序遍历的时候，会发现套路又不一样了，目前的前序遍历的逻辑无法直接应用到中序遍历上。

（2）、中序遍历

为了解释清楚，我说明一下 刚刚在迭代的过程中，其实我们有两个操作：

1.处理：将元素放进result数组中
2.访问：遍历节点

分析一下为什么刚刚写的前序遍历的代码，不能和中序遍历通用呢，因为前序遍历的顺序是中左右，先访问的元素是中间节点，要处理的元素也是中间节点，所以刚刚才能写出相对简洁的代码，因为要访问的元素和要处理的元素顺序是一致的，都是中间节点。

那么再看看中序遍历，中序遍历是左中右，先访问的是二叉树顶部的节点，然后一层一层向下访问，直到到达树左面的最底部，再开始处理节点（也就是在把节点的数值放进result数组中），这就造成了处理顺序和访问顺序是不一致的。

那么在使用迭代法写中序遍历，就需要借用指针的遍历来帮助访问节点，栈则用来处理节点上的元素。

动画如下：
请添加图片描述
中序遍历，可以写出如下代码：

# 中序遍历-迭代-LC94_二叉树的中序遍历
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        stack = []  # 不能提前将root结点加入stack中
        result = []
        cur = root
        while cur or stack:
            # 先迭代访问最底层的左子树结点
            if cur:     
                stack.append(cur)
                cur = cur.left		
            # 到达最左结点后处理栈顶结点    
            else:		
                cur = stack.pop()
                result.append(cur.val)
                # 取栈顶元素右结点
                cur = cur.right	
        return result

（3）、后序遍历

再来看后序遍历，先序遍历是中左右，后续遍历是左右中，那么我们只需要调整一下先序遍历的代码顺序，就变成中右左的遍历顺序，然后在反转result数组，输出的结果顺序就是左右中了，如下图：
在这里插入图片描述
所以后序遍历只需要前序遍历的代码稍作修改就可以了，代码如下：

# 后序遍历-迭代-LC145_二叉树的后序遍历
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        stack = [root]
        result = []
        while stack:
            node = stack.pop()
            # 中结点先处理
            result.append(node.val)
            # 左孩子先入栈
            if node.left:
                stack.append(node.left)
            # 右孩子后入栈
            if node.right:
                stack.append(node.right)
        # 将最终的数组翻转
        return result[::-1]

总结：
此时我们用迭代法写出了二叉树的前后中序遍历，大家可以看出前序和中序是完全两种代码风格，并不像递归写法那样代码稍做调整，就可以实现前后中序。

这是因为前序遍历中访问节点（遍历节点）和处理节点（将元素放进result数组中）可以同步处理，但是中序就无法做到同步！

上面这句话，可能一些同学不太理解，建议自己亲手用迭代法，先写出来前序，再试试能不能写出中序，就能理解了。

那么问题又来了，难道 二叉树前后中序遍历的迭代法实现，就不能风格统一么（即前序遍历 改变代码顺序就可以实现中序 和 后序）？

当然可以，这种写法，还不是很好理解。


1.7、二叉树的统一迭代法

前面一节无法同时解决访问节点（遍历节点）和处理节点（将元素放进结果集）不一致的情况。

那我们就将访问的节点放入栈中，把要处理的节点也放入栈中但是要做标记。

如何标记呢，就是要处理的节点放入栈之后，紧接着放入一个空指针作为标记。 这种方法也可以叫做标记法。

（1）、前序遍历

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        result = []
        st= []
        if root:
            st.append(root)
        while st:
            node = st.pop()
            if node != None:
                if node.right: #右
                    st.append(node.right)
                if node.left: #左
                    st.append(node.left)
                st.append(node) #中
                st.append(None)
            else:
                node = st.pop()
                result.append(node.val)
        return result

（2）、中序遍历

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        result = []
        st = []
        if root:
            st.append(root)
        while st:
            node = st.pop()
            if node != None:
                if node.right: #添加右节点（空节点不入栈）
                    st.append(node.right)
                
                st.append(node) #添加中节点
                st.append(None) #中节点访问过，但是还没有处理，加入空节点做为标记。
                
                if node.left: #添加左节点（空节点不入栈）
                    st.append(node.left)
            else: #只有遇到空节点的时候，才将下一个节点放进结果集
                node = st.pop() #重新取出栈中元素
                result.append(node.val) #加入到结果集
        return result

（3）、后序遍历

class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        result = []
        st = []
        if root:
            st.append(root)
        while st:
            node = st.pop()
            if node != None:
                st.append(node) #中
                st.append(None)
                
                if node.right: #右
                    st.append(node.right)
                if node.left: #左
                    st.append(node.left)
            else:
                node = st.pop()
                result.append(node.val)
        return result

1.8、二叉树的层序遍历

层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。

需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。

使用队列实现二叉树广度优先遍历，动画如下：
请添加图片描述
递归法：

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        res = []
        def helper(root, depth):
            if not root: 
            	return []
            if len(res) == depth: 
            	res.append([]) # start the current depth
            res[depth].append(root.val) # fulfil the current depth
            if  root.left: 
            	helper(root.left, depth + 1) # process child nodes for the next depth
            if  root.right: 
            	helper(root.right, depth + 1)
        helper(root, 0)
        return res

迭代法：

class Solution:
    """二叉树层序遍历迭代解法"""

    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        results = []
        if not root:
            return results

        from collections import deque
        que = deque([root])

        while que:
            size = len(que)
            result = []
            for _ in range(size):
                cur = que.popleft()
                result.append(cur.val)
                if cur.left:
                    que.append(cur.left)
                if cur.right:
                    que.append(cur.right)
            results.append(result)

        return results


二、经典例题

2.1、前中后序遍历

144.二叉树的前序遍历

class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []

        def traversal(cur):
            if not cur:
                return
            res.append(cur.val)
            traversal(cur.left)
            traversal(cur.right)
        traversal(root)
        return res

94.二叉树的中序遍历

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []

        def traversal(cur):
            if not cur:
                return
            traversal(cur.left)
            res.append(cur.val)
            traversal(cur.right)
        traversal(root)
        return res

145.二叉树的后序遍历

class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        res = []

        def traversal(cur):
            if not cur:
                return
            traversal(cur.left)
            traversal(cur.right)
            res.append(cur.val)
        traversal(root)
        return res

2.2、层序遍历

102.二叉树的层序遍历

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        res = []

        def traversal(cur, height):
            if not cur:
                return
            if len(res)==height:
                res.append([])
            res[height].append(cur.val)
            traversal(cur.left, height+1)
            traversal(cur.right, height+1)
        traversal(root, 0)
        return res

107.二叉树的层次遍历II

class Solution:
    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        res = []

        def traversal(cur, height):
            if not cur:
                return
            if len(res)==height:
                res.append([])
            res[height].append(cur.val)
            traversal(cur.left, height+1)
            traversal(cur.right, height+1)
        traversal(root, 0)
        return res[::-1]

199.二叉树的右视图

还是先层序遍历，取每一层list的-1值即可。

class Solution:
    def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
        res = []

        def traversal(cur,height):
            if not cur:
                return
            if len(res)==height:
                res.append([])
            res[height].append(cur.val)
            traversal(cur.left, height+1)
            traversal(cur.right, height+1)
        traversal(root, 0)
        result=[]
        for r in res:
            result.append(r[-1])
        return result

637.二叉树的层平均值

class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        res = []
        def traversal(cur, height):
            if not cur:
                return
            if len(res)==height:
                res.append([])
            res[height].append(cur.val)
            traversal(cur.left, height+1)
            traversal(cur.right, height+1)
        traversal(root, 0)
        result = []
        for r in res:
            result.append(sum(r)/len(r))
        return result

429.N叉树的层序遍历

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        res = []
        def traversal(cur, height):
            if not cur:
                return
            if len(res)==height:
                res.append([])
            res[height].append(cur.val)
            for tree in cur.children:
                traversal(tree, height+1)
        traversal(root, 0)
        return res

515.在每个 树行中找最大值

class Solution:
    def largestValues(self, root: Optional[TreeNode]) -> List[int]:
        res = []
        def traversal(cur, height):
            if not cur:
                return
            if len(res)==height:
                res.append([])
            res[height].append(cur.val)
            traversal(cur.left, height+1)
            traversal(cur.right, height+1)
        traversal(root, 0)

        return [max(r) for r in res]

116.填充每个节点的下一个右侧节点指针

把每个节点存起来，每一层进行连接

class Solution:
    def connect(self, root: 'Optional[Node]') -> 'Optional[Node]':
        res = []
        def traversal(cur, height):
            if not cur:
                return
            if len(res)==height:
                res.append([])
            res[height].append(cur)
            traversal(cur.left, height+1)
            traversal(cur.right, height+1)
        traversal(root,0)
        for r in res:
            for i in range(len(r)-1):
                r[i].next=r[i+1]
            r[-1].next=None
        return root

117.填充每个节点的下一个右侧节点指针II

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        res = []
        def traversal(cur, height):
            if not cur:
                return
            if len(res)==height:
                res.append([])
            res[height].append(cur)
            traversal(cur.left, height+1)
            traversal(cur.right, height+1)
        traversal(root, 0)

        for r in res:
            for i in range(len(r)-1):
                r[i].next=r[i+1]
        return root

104.二叉树的最大深度

104.二叉树的最大深度
按照层序遍历模板解题：

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        res = 0
        def traversal(cur, height):
            if not cur:
                return
            # 叶子节点为深度
            if not cur.left and not cur.right:
                nonlocal res
                # 要+1，从0开始
                res = max(res, height+1)
                return
            traversal(cur.left, height+1)
            traversal(cur.right, height+1)
        traversal(root, 0)
        return res

正规官方解法：

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        else:
            left_height = self.maxDepth(root.left)
            right_height = self.maxDepth(root.right)
            return max(left_height, right_height)+1

111.二叉树的最小深度

111.二叉树的最小深度

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        res = float('inf')
        def traversal(cur, height):
            if not cur:
                return
            # 叶子节点
            if not cur.left and not cur.right:
                nonlocal res
                res = min(res, height+1)
                return
            traversal(cur.left, height+1)
            traversal(cur.right, height+1)
        traversal(root, 0)
        return res if root else 0

2.3、其他类型

617.合并二叉树

617.合并二叉树

class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        def traversal(cur1, cur2):
            if not cur1 and not cur2:
                return
            if cur1 and cur2:
                cur1.val+=cur2.val
            if not cur1 and cur2:
                return cur2
            if cur1 and not cur2:
                return cur1
            cur1.left = traversal(cur1.left,cur2.left)
            cur1.right = traversal(cur1.right, cur2.right)
            return cur1
        root1 = traversal(root1, root2)
        return root1

105. 从前序与中序遍历序列构造二叉树

105. 从前序与中序遍历序列构造二叉树
同上，寻找递归部分。
前序遍历，根节点永远在头部第一个位置。
中序遍历，根节点通过前序遍历去定位位置，然后左边全部打包当做左子树，右边也同样打包当做右子树。

通过前序遍历寻找根节点，通过中序遍历接上前面的根节点去划分左右子树，去构造题目要求的源二叉树。

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        def traversal(preorder, inorder):
            if not preorder or not inorder:
                return None
            root = TreeNode(preorder[0])
            ind = inorder.index(preorder[0])
            # 以根节点划分为左右两边
            # 前序遍历根在第一个，去掉
            # 那么左子树，前序遍历从1到ind+1，中序遍历从头到ind
            root.left = traversal(preorder[1:ind+1], inorder[:ind])
            # 右子树，前序遍历从ind+1到结尾，中序遍历跳过中间root，为ind+1到结尾
            root.right = traversal(preorder[ind+1:], inorder[ind+1:])
            return root
        return traversal(preorder, inorder)

参考1
参考2

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

106.从中序与后序遍历序列构造二叉树
该题同上，中序还是一样，后序变成尾部为第一个根节点。其次每次划分的切片进行更改，其余步骤一样。

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        def traversal(inorder, postorder):
            if not inorder or not postorder:
                return None
            tree = TreeNode(postorder[-1])
            index = inorder.index(postorder[-1])
            # 左子树，中序遍历到index，后序遍历到index
            tree.left = traversal(inorder[:index], postorder[:index])
            # 右子树，中序遍历从index+1到结尾，除掉index位置的根节点
            # 后序遍历从index到-1，除掉-1位置的根节点
            tree.right = traversal(inorder[index+1:], postorder[index:-1])
            return tree
        return traversal(inorder, postorder)

剑指 Offer 68 - II. 二叉树的最近公共祖先

剑指 Offer 68 - II. 二叉树的最近公共祖先

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        def traversal(cur, p, q):
            # 找不到节点，该树不含有p或q
            if not cur:
                return None
            # 根节点为其中一个，则直接返回那个节点
            if cur==p or cur==q:
                return cur
            # 根据p和q在左右子树状态位置去得出答案
            left = traversal(cur.left, p, q)
            right = traversal(cur.right, p, q)
            if not left and not right:
                return None
            if not left:
                return right
            if not right:
                return left
            # if right and left:
            return cur
        return traversal(root,p,q)

简写：

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        def traversal(cur, p, q):
            # 合并到下面，return cur的cur也是None
            #if not cur:
            #    return None
            
            if not cur or cur==p or cur==q:
                return cur
            
            left = traversal(cur.left, p, q)
            right = traversal(cur.right, p, q)
            # 与if not cur重复
            #if not left and not right:
            #    return None
            if not left:
                return right
            if not right:
                return left
            return cur
        return traversal(root,p,q)

参考1

235. 二叉搜索树的最近公共祖先

235. 二叉搜索树的最近公共祖先
剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
搜索树的节点值是有序的，直接根据值去判断左右树是否有p和q，而不用继续深度遍历到该p和q节点。

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        def traversal(cur, p, q):
            if p.val<cur.val and q.val<cur.val:
                return traversal(cur.left,p,q)
            if p.val>cur.val and q.val>cur.val:
                return traversal(cur.right,p,q)
            return cur
        return traversal(root,p,q)

参考1

98.验证二叉搜索树

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:

        def traversal(cur, lower=float('-inf'), upper=float('inf')):
            if not cur:
                return True
            if cur.val<=lower or cur.val>=upper:
                return False
            
            left = traversal(cur.left, lower, cur.val)
            right = traversal(cur.right, cur.val, upper)
            if not left or not right:
                return False
            return True
        return traversal(root)

参考1
参考2

652. 寻找重复的子树

652. 寻找重复的子树

class Solution:
    def findDuplicateSubtrees(self, root: Optional[TreeNode]) -> List[Optional[TreeNode]]:
        st = dict()
        ans = list()

        def dfs(root):
            if not root:
                return ""
            left = dfs(root.left)
            right = dfs(root.right)
            cur = "_".join((str(root.val), left, right))
            if cur not in st:
                st[cur] = 1
            else:
                st[cur] += 1
            if st[cur] == 2:
                ans.append(root)
            return cur
        
        dfs(root)
        return ans

2.4、其他经典练习题

226.翻转二叉树

101. 对称二叉树

104.二叉树的最大深度

111.二叉树的最小深度

222.完全二叉树的节点个数

110.平衡二叉树

257. 二叉树的所有路径

404.左叶子之和

513.找树左下角的值

112. 路径总和

654.最大二叉树

700.二叉搜索树中的搜索

530.二叉搜索树的最小绝对差

501.二叉搜索树中的众数

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

701.二叉搜索树中的插入操作

450.删除二叉搜索树中的节点

669. 修剪二叉搜索树

108.将有序数组转换为二叉搜索树

538.把二叉搜索树转换为累加树