[数据结构与算法]【编程之路】面试必刷TOP101：二叉树系列（31-36，Python实现）

面试必刷TOP101：二叉树系列（31-36，Python实现）

31.对称的二叉树（小试牛刀）

31.1 递归法

step 1：两种方向的前序遍历，同步过程中的当前两个节点，同为空，属于对称的范畴。
step 2：当前两个节点只有一个为空或者节点值不相等，已经不是对称的二叉树了。
step 3：第一个节点的左子树与第二个节点的右子树同步递归对比，第一个节点的右子树与第二个节点的左子树同步递归比较。

class Solution:
    def recursion(self, root1: TreeNode, root2: TreeNode):
        if root1 == None and root2 == None:
            return True
        if root1 == None or root2 == None or root1.val != root2.val:
            return False
        return self.recursion(root1.left, root2.right) and self.recursion(root1.right, root2.left)
    def isSymmetrical(self , pRoot: TreeNode) -> bool:
        return self.recursion(pRoot, pRoot)

时间复杂度：O(n)，其中 n 为二叉树的节点数，相当于遍历整个二叉树两次。
空间复杂度：O(n)，最坏情况二叉树退化为链表，递归栈深度为 n。

31.2 层次遍历 / 队列

step 1：首先判断链表是否为空，空链表直接就是对称。
step 2：准备两个队列，分别作为从左往右层次遍历和从右往左层次遍历的辅助容器，初始第一个队列加入左节点，第二个队列加入右节点。
step 3：循环中每次从队列分别取出一个节点，如果都为空，暂时可以说是对称的，进入下一轮检查；如果某一个为空或是两个节点值不同，那必定不对称。其他情况暂时对称，可以依次从左往右加入子节点到第一个队列，从右往左加入子节点到第二个队列。（这里包括空节点）
step 4：遍历结束也没有检查到不匹配，说明就是对称的。

import queue
class Solution:
    def isSymmetrical(self , pRoot: TreeNode) -> bool:
        if pRoot == None:
            return True
        q1 = queue.Queue()
        q2 = queue.Queue()
        q1.put(pRoot.left)
        q2.put(pRoot.right)
        while not q1.empty() and not q2.empty():
            a = q1.get()
            b = q2.get()
            # 如果都为空，暂时对称，注意不能在此处直接返回 True
            if a is None and b is None:
                continue 
            if a is None or b is None or a.val != b.val:
                return False
            # 左子树从左往右加入队列
            q1.put(a.left)
            q1.put(a.right)
            # 右子树从右往左加入队列
            q2.put(b.right)
            q2.put(b.left)
        # 都检验完是对称的
        return True

时间复杂度：O(n)，其中 n 为二叉树的节点个数，相当于遍历二叉树全部节点。
空间复杂度：O(n)，两个辅助队列的最大空间为 n。

32.合并二叉树（小试牛刀）

32.1 递归法

step 1：首先判断 t1 与 t2 是否为空，若为则用另一个代替，若都为空，返回的值也是空。
step 2：然后依据前序遍历的特点，优先访问根节点，将两个根点的值相加创建到新树中。
step 3：两棵树再依次同步进入左子树和右子树。

class Solution:
    def mergeTrees(self , t1: TreeNode, t2: TreeNode) -> TreeNode:
        if t1 is None:
            return t2
        if t2 is None:
            return t1
        head = TreeNode(t1.val+t2.val)
        head.left = self.mergeTrees(t1.left,t2.left)
        head.right = self.mergeTrees(t1.right,t2.right)
        return head

时间复杂度：O(min(n, m))，m 和 n 分别为两棵树的节点树，当一个树访问完时，自然就连接上另一个树的节点，故只访问了小树的节点数。
空间复杂度：O(min(n, m))，递归栈深度也同时间，只访问了小树的节点数。

32.2 辅助队列

step 1：首先判断 t1 与 t2 是否为空，若为则用另一个代替，若都为空，返回的值也是空。
step 2：使用三个辅助队列，第一个队列 q 用于暂存合并后的二叉树的层次遍历节点，第二个队列 q1 用于暂存 t1 的层次遍历节点，第三个队列 q2 用于暂存 t2 的层次遍历节点。
step 3：两棵树同步层次遍历，先将根节点加入队列中，同时根节点优先合并。
step 4：每次从队列分别弹出一个元素，判断分别二者的左右子节点是否存在，若是都存在，则相加合并，若是只存在一个则连接该存在的节点，若是都不存在则连接 null。

import queue
class Solution:
    def mergeTrees(self , t1: TreeNode, t2: TreeNode) -> TreeNode:
        if t1 is None:
            return t2
        if t2 is None:
            return t1
        head = TreeNode(t1.val+t2.val)
        # 存放连接后的树的层次遍历结点
        q = queue.Queue()
        # 分别存放两棵树的层次遍历结点
        q1 = queue.Queue()
        q2 = queue.Queue()
        q.put(head)
        q1.put(t1)
        q2.put(t2)
        while not q1.empty() and not q2.empty():
            node = q.get()
            node1 = q1.get()
            node2 = q2.get()
            left1 = node1.left
            left2 = node2.left
            right1 = node1.right
            right2 = node2.right
            if left1 or left2:
                if left1 and left2:
                    left_new = TreeNode(left1.val+left2.val)
                    node.left = left_new
                    q.put(left_new)
                    q1.put(left1)
                    q2.put(left2)
                elif left1:
                    node.left = left1
                elif left2:
                    node.left = left2
            if right1 or right2:
                if right1 and right2:
                    right_new = TreeNode(right1.val+right2.val)
                    node.right = right_new
                    q.put(right_new)
                    q1.put(right1)
                    q2.put(right2)
                elif right1:
                    node.right = right1
                elif right2:
                    node.right = right2
        return head

时间复杂度：O(min(n, m))，m 和 n 分别为两棵树的节点树，当一个树访问完时，自然就连接上另一个树的节点，故只访问了小树的节点数。
空间复杂度：O(min(n, m))，辅助队列同时间，只访问了小树的节点数。

33.二叉树的镜像（小试牛刀）

33.1 递归法

step 1：先深度最左端的节点，遇到空树返回，处理最左端的两个子节点交换位置。
step 2：然后进入右子树，继续按照先左后右再回中的方式访问。
step 3：再返回到父问题，交换父问题两个子节点的值。

class Solution:
    def Mirror(self , pRoot: TreeNode) -> TreeNode:
        if not pRoot:
            return None
        # 先递归子树
        left = self.Mirror(pRoot.left)
        right = self.Mirror(pRoot.right)
        # 交换
        pRoot.left = right
        pRoot.right = left
        return pRoot

时间复杂度：O(n)，其中 n 为二叉树的节点数，访问二叉树所有节点各一次。
空间复杂度：O(n)，最坏情况下，二叉树退化为链表，递归栈最大值为 n。

33.2 辅助栈

step 1：优先检查空树的情况。
step 2：使用栈辅助遍历二叉树，根节点先进栈。
step 3：遍历过程中每次弹出栈中一个元素，然后该节点左右节点分别入栈。
step 4：同时我们交换入栈两个子节点的值，因为子节点已经入栈了再交换，就不怕后续没有交换。

class Solution:
    def Mirror(self , pRoot: TreeNode) -> TreeNode:
        if not pRoot:
            return None
        a = []
        a.append(pRoot)
        while a:
            node = a.pop()
            if node.left:
                a.append(node.left)
            if node.right:
                a.append(node.right)
            node.left, node.right = node.right, node.left
        return pRoot

时间复杂度：O(n)，其中 n 为二叉树的节点数，访问二叉树所有节点各一次。
空间复杂度：O(n)，最坏情况下，二叉树退化为链表，栈的最大空间为 n。

34.判断是不是二叉搜索树（小试牛刀）

34.1 递归法

二叉搜索树的特性就是中序遍历是递增序。既然是判断是否是二叉搜索树，那我们可以使用中序递归遍历。只要之前的节点是二叉树搜索树，那么如果当前的节点小于上一个节点值那么就可以向下判断。只不过在过程中我们要求反退出。比如一个链表1->2->3->4，只要 for 循环遍历如果中间有不是递增的直接返回 false 即可。
step 1：首先递归到最左，初始化 maxLeft 与 pre。
step 2：然后往后遍历整棵树，依次连接 pre 与当前节点，并更新 pre。
step 3：左子树如果不是二叉搜索树返回 false。
step 4：判断当前节点是不是小于前置节点，更新前置节点。
step 5：最后由右子树的后面节点决定。

import sys
class Solution:
    pre = -sys.maxsize - 1
    def isValidBST(self , root: TreeNode) -> bool:
        if root == None:
            return True
        # 先进入左子树
        if not self.isValidBST(root.left):
            return False
        if root.val <= self.pre:
            return False
        # 更新最值
        self.pre = root.val
        # 再进入右子树
        if not self.isValidBST(root.right):
            return False
        return True

34.2 辅助栈

step 1：优先判断树是否为空，空树不遍历。
step 2：准备一个数组记录中序遍历的结果。
step 3：准备辅助栈，当二叉树节点为空了且栈中没有节点了，我们就停止访问。
step 4：从根节点开始，每次优先进入每棵的子树的最左边一个节点，我们将其不断加入栈中，用来保存父问题。
step 5：到达最左后，可以开始访问，如果它还有右节点，则将右边也加入栈中，之后右子树的访问也是优先到最左。
step 6：遍历数组，依次比较相邻两个元素是否为递增序。

class Solution:
    def isValidBST(self , root: TreeNode) -> bool:
        a = [] # 该栈用于辅助遍历
        b = [] # 用于记录中序遍历的结果
        head = root
        while head or a:
            while head: # 走到最左
                a.append(head)
                head = head.left
            res = a.pop()
            b.append(res.val)
            head = res.right
        # 遍历中序结果
        for i in range(1,len(b)):
            if b[i-1] >= b[i]:
                return False
        return True

时间复杂度：O(n)，其中 n 为二叉树的节点数，遍历整个二叉树后又遍历数组。
空间复杂度：O(n)，辅助栈及辅助数组的空间最坏为 O(n)。

35.判断是不是完全二叉树（小试牛刀）

35.1 层次遍历

step 1：先判断空树一定是完全二叉树。
step 2：初始化一个队列辅助层次遍历，将根节点加入。
step 3：逐渐从队列中弹出元素访问节点，如果遇到某个节点为空，进行标记，代表到了完全二叉树的最下层，若是后续还有访问，则说明提前出现了叶子节点，不符合完全二叉树的性质。
step 4：否则，继续加入左右子节点进入队列排队，等待访问。

import queue
class Solution:
    def isCompleteTree(self , root: TreeNode) -> bool:
        # 空树一定是完全二叉树
        if root == None:
            return True
        q = queue.Queue()
        q.put(root)
        flag = False # 定义一个首次出现空结点的标记位
        while not q.empty():
            cur = q.get()
            if not cur: # 第一次出现为空的地方进行标记
                flag = True
            else:
                if flag:
                    return False
                q.put(cur.left)
                q.put(cur.right)
        return True

另一种写法。

class Solution:
    def isCompleteTree(self , root: TreeNode) -> bool:
        # 空树一定是完全二叉树
        if root == None:
            return True
        a = []
        a.append(root)
        count = 0
        while count < len(a):
            if a[count] is not None:
                a.append(a[count].left)
                a.append(a[count].right)
            count = count + 1
        while a[-1] is None:
            a.pop()
        for item in a:
            if item is None:
                return False
        return True

时间复杂度：O(n)，其中 n 为二叉树节点数，层次遍历最坏情况下遍历每一个节点。
空间复杂度：O(n)，最坏情况下，层次队列的最大空间为 O(n)。

36.判断是不是平衡二叉树（小试牛刀）

36.1 自顶向下

step 1：第一个函数递归遍历二叉树所有节点。
step 2：对于每个节点判断，调用第二个函数获取子树深度。
step 3：第二个函数递归获取子树深度，只需要不断往子节点深度遍历，累加左右深度的较大值。
step 4：根据深度判断该节点下的子树是否为平衡二叉树。

class Solution:
    # 计算子树深度
    def deep(self, root: TreeNode):
        if not root:
            return 0
        left = self.deep(root.left)
        right = self.deep(root.right)
        # 子树的最大深度 + 1
        return left + 1 if left > right else right + 1
    def IsBalanced_Solution(self , pRoot: TreeNode) -> bool:
        if pRoot is None:
            return True
        left = self.deep(pRoot.left)
        right = self.deep(pRoot.right)
        if left - right > 1 or right - left > 1:
            return False
        return self.IsBalanced_Solution(pRoot.left) and self.IsBalanced_Solution(pRoot.right)

时间复杂度：O($n^2$)，其中 n 为二叉树的节点数，第一个递归遍历二叉树所有节点，第二个递归查找深度最坏情况下（二叉树退化为链表）需要遍历二叉树所有节点。
空间复杂度：O($n$)，递归栈最大深度为 n。

36.2 自底向上

上述一个函数算深度，一个函数遍历所有节点的方法，用了两个递归，做了很多不必要的运算，这就是自顶向下的弊端。那我们可以考虑自底向上，因为其实我们判断某个节点是否符合平衡二叉树特性的时候，需要的不是左右子树的完整深度，而是深度差，只要深度差绝对值不超过1，就可以满足。因此在底部计算深度的同时，判断该子树是否为平衡二叉树，将是或否与深度差一起往上传就行。

step 1：先判断空树，直接为平衡二叉树。
step 2：递归进行边计算深度边判断是否平衡二叉树。
step 3：递归计算当前节点左右子树的深度差，然后比较深度差是否符合平衡二叉树。
step 4：每次递归都将深度结果往上传，遇到不符合平衡二叉树的，返回-1，而深度差我们取绝对值保证返回正数，因此最后的负数一定就是 不满足条件，这样就能做到边判断边计算深度了。

class Solution:
    def deep(self, root: TreeNode):
        if not root:
            return 0
        left = self.deep(root.left)
        if left < 0: return -1
        right = self.deep(root.right)
        if right < 0: return -1
        return -1 if abs(left - right) > 1 else max(left, right) + 1
        
    def IsBalanced_Solution(self , pRoot: TreeNode) -> bool:
        if not pRoot:
            return True
        return self.deep(pRoot) != -1

时间复杂度：O(n)，其中 n 为树的节点数，一次递归遍历二叉树所有节点。
空间复杂度：O(n)，最坏情况下递归栈的深度为 n。