二叉树算法精讲：Python 递归与迭代实现深度解析

第一时间捕获有价值的信号

深入理解二叉树算法，涵盖最小深度、节点计数、层平均值、直径、平衡性与对称性判断。通过 Python 递归与迭代实现，助你掌握核心数据结构算法。

核心内容

二叉树的题目普遍可以用递归和迭代的方式解决树.jpg

其他分类方式

基础算法

二叉树的最小深度

class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        if root.left==None or root.right==None:
            return self.minDepth(root.left)+self.minDepth(root.right)+1
        else:
            return min(map(self.minDepth,(root.left,root.right)))+1

完全二叉树中节点的个数

# 深度遍历(递归法)
class Solution:
    def countNodes(self, root: TreeNode) -> int:
        return 1+self.countNodes(root.left)+self.countNodes(root.right) if root else 0
# 广度遍历(层序)
class Solution:
    def countNodes(self, root: TreeNode) -> int:
        count=0
        if root:
            level=[root]
            while level:
                count+=len(level)
                level=[kid for node in level for kid in (node.left,node.right) if kid]
        return count

二叉树的层平均值

class Solution:
    def averageOfLevels(self, root: TreeNode) -> List[float]:
        average=[]
        if root:
            level=[root]
            while level:
                average.append(sum(i.val for i in level)/len(level))
                level=[kid for node in level for kid in (node.left,node.right) if kid]
        return average

二叉树的直径

采用分治和递归的思想：根节点为root的二叉树的直径 = max(root-left的直径, root->right的直径，root->left的最大深度+root->right的最大深度+1)
分两种情况，1，最大直径经过根节点，则直径为左子树最大深度+右子树最大深度 2.如果不经过根节点，则取左子树或右子树的最大深度

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.diameter=0
        def dfs(root):
            if root==None:
                return 0
            left=dfs(root.left)
            right=dfs(root.right)
            self.diameter=max(self.diameter,left+right)
            return max(left,right)+1
        dfs(root)
        return self.diameter

判断二叉树是否是平衡二叉树

#一般认为平衡二叉树空间复杂度是O(logn)的，这是因为平衡二叉树的高度h就是O(logn)级别的。但是对于一般的树，严谨起见，还是要说O(h)的。这个h可能是logn（最好情况），也可能是n（最坏情况））

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        def check_depth(root):
            if root==None:
                return 0
            left_depth=check_depth(root.left)
            right_depth=check_depth(root.right)
            return max(left_depth,right_depth)+1
        if root==None:
            return True
        return abs(check_depth(root.left)-check_depth(root.right))<=1 and self.isBalanced(root.left) and self.isBalanced(root.right)

两个二叉树是否完全相同

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if p and q:
            # 两棵二叉树均不为空，如果根节点的值相等，左子树相等和右子树相等，则这两棵二叉树相等，否则不相等。
            return p.val==q.val and self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right)
        return p is q
# 最后一句相当于以下两种情况
if not p and not q: # 两棵树均为空
    return True
if not p and q or not q and p:  # 两棵树只有一棵为空
    return False

对称二叉树

class Solution:
    def isSymmetric(self, root: TreeNode) -> bool:
        def isSym(l,r):
            # 左右节点同时为空
            if not l and not r:
                return True
            # 左右节点相等，继续递归求解是否为镜像
            if l and r and l.val==r.val:
                return isSym(l.left,r.right) and isSym(l.right,r.left)
            # 其他情况均不是对称树
            return False
        return isSym(root,root)

两个二叉树的最低公共祖先节点

# 思路：递归，如果当前节点就是p或q，说明当前节点就是最近的祖先；如果当前节点不是p或p，就试着从左右子树里找pq；如果pq分别在一左一右被找到，那么当前节点还是最近的祖先返回root就好了；否则，返回它们都在的那一边。
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if root==None:   
            return 
        if root==p or root==q:
            return root
        left=self.lowestCommonAncestor(root.left,p,q)
        right=self.lowestCommonAncestor(root.right,p,q)
        if left and right:
            return root
        if left:
            return left
        if right:
            return right
        else:
            return

四种遍历方式

二叉树的四种遍历方式分别是：前序、中序、后序和层次。它们的时间复杂度都是O(n)，其中n是树中节点个数，因为每一个节点在递归的过程中，只访问了一次。
三种深度优先遍历方法的空间复杂度是O(h)，其中h是二叉树的深度，额外空间是函数递归的调用栈产生的，而不是显示的额外变量。空间复杂度，通常是指完成算法所用的辅助空间的复杂度，而不用管算法前置的空间复杂度。比如在树的遍历算法中，整棵树肯定要占O(n)的空间，n是树中节点的个数，这部分空间是“平凡”的，即肯定存在的，我们不讨论它。
层次遍历的空间复杂度是O(w)，其中w是二叉树的宽度（拥有最多节点的层的节点数）。

二叉树的前序遍历

# 递归解法
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        ret=[]
        if root:
            ret=ret+[root.val]
            ret=ret+self.preorderTraversal(root.left)
            ret=ret+self.preorderTraversal(root.right)
        return ret
# 迭代算法思路：使用栈的思想，从根节点开始以此使用ret添加根节点值，stack添加右节点，curr=左节点，如果左节点为None，则获取其上一个右节点（一直输出根节点，添加其右节点，遍历左节点，右节点的输出顺序为从下往上）
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        ret=[]
        if root==None:
            return ret
        stack=[]
        curr=root
        while curr or stack:
            if curr:
                ret.append(curr.val)
                stack.append(curr.right)
                curr=curr.left
            else:
                curr=stack.pop()
        return ret

二叉树的中序遍历

# 递归解法同上
# 迭代解法
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        res=[]
        if root==None:
            return res
        stack=[]  #添加根节点
        curr=root
        while curr or stack:
            if curr:
                stack.append(curr)
                curr=curr.left
            else:
                curr=stack.pop()
                res.append(curr.val)
                curr=curr.right
        return res

二叉树的后序遍历

# 递归解法同上
# 迭代算法思路：后序遍历方式为：左右中，将其进行反转 中右左，那么我们可以实现一个中右左，其原理与前序遍历一样
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        ret=[]
        if root==None:
            return ret
        stack=[]
        curr=root
        while curr or stack:
            if curr:
                ret.append(curr.val)
                stack.append(curr.left)
                curr=curr.right
            else:
                curr=stack.pop()
        return ret[::-1]

二叉树的层次遍历

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        level=[root]
        ret=[]
        if root==None:
            return []
        while level:
            ret.append([i.val for i in level])
            level=[kid for node in level for kid in (node.left,node.right) if kid]
        return ret

进阶算法

不同的二叉树

分析：采用动态规划解决，假设用G(n)表示前n个整数的二叉搜索树的总数，F（i）表示当i节点为根节点的二叉搜索树的个数，当i为根节点时，由于二叉搜索树的规则，前i-1个节点都应该位于以i节点为根节点的左子树，i+1以后的节点都应该位于右子树，那么由咱们的假设可知，由前i-1个节点构成的左子树的二叉搜索树的总数为G(i-1)，同理右子树的二叉搜索树的总数为G（n-i），所以以i为根节点的二叉搜索树的总数F(i) = G(i-1)*G(n-i)，则前n个节点的所有二叉搜索树总数G(n） = F(1)+F(2)+…+F(n)。可以采用动态规划完成。

class Solution:
    def numTrees(self, n: int) -> int:
        # n=0,n=1的情况
        g=[1,1]
        for i in range(2,n+1):
            f=0
            for j in range(1,i+1):
                #若i为3：g[0]*g[3]+g[1]*g[2]+g[2]*g[1]+g[3]*g[0]
                f+=g[j-1]*g[i-j]
            g.append(f)
        return g[-1]

验证二叉搜索树(BST)

一棵BST定义为：节点的左子树中的值要严格小于该节点的值，节点的右子树中的值要严格大于该节点的值，左右子树也必须是二叉查找树，一个节点的树也是二叉查找树。

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        output=[]
        self.inOrder(root,output)
        for i in range(1,len(output)):
            if output[i-1]>=output[i]:
                return False
        return True
    def inOrder(self,root,output):
        if root==None:
            return
        # 利用中序遍历，自下而上升序排列
        self.inOrder(root.left,output)
        output.append(root.val)
        self.inOrder(root.right,output)

前序遍历和中序遍历构造二叉树（实现参考）

前序的第一个节点必定是根节点，在中序遍历中找到根节点所在的索引x，观察研究可以发现，在中序遍历中根节点索引之前的即为其左孩子，即左孩子们 = root[:x];那么在前序遍历中的左孩子个数和中序遍历是一样的，即为从前序遍历中索引为1（索引0为根节点）到x+1的节点；其余的则为右孩子们。最后递归调用自己，得到二叉树

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if preorder==[]:
            return None
        # 找到根节点在中序遍历中的位置(索引)
        index=inorder.index(preorder[0])
        root = TreeNode(preorder[0])
        # 递归调用
        root.left=self.buildTree(preorder[1:index+1],inorder[0:index])
        root.right=self.buildTree(preorder[index+1:],inorder[index+1:])
        return root