二叉树的前、中、后、层序遍历

有一棵二叉树的结构如下图所示：

则前、中、后遍历对应的规则可以表示为：

• 前序遍历：先根、再左、再右，即：ABDEGCF
• 中序遍历：先左、再根、再右，即DBGEACF
• 后序遍历：先左、再右、再根，即：DGEBFCA
• 层序遍历：按树的层次搜索，即：
  ABCDEFG

解题思路

前、中、后序的遍历可以用深度优先搜索解决，可以使用递归函数或者单调栈解决。递归函数在计算机中实现隐式的利用了被称为调用栈的栈，即递归利用了栈，只是隐式的利用了栈，没有显示的让你看到其使用了栈。以中序遍历为例，整体过程为访问结点并入栈遍历左子树，出栈遍历右子树。

也可以辅助栈将上面递归函数隐式调用栈的过程显示表示。以中序遍历为例，实现访问结点并入栈遍历左子树，结点出栈遍历右子树。

层序遍历可以使用宽度优先搜索算法解决，即构造一个辅助队列，当队列不为空时，弹出当前节点，并将当前节点的左右节点加入到队列中。

案例代码

递归思路

#前序遍历
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        def preorder(root: TreeNode):
            if not root:
                return
            res.append(root.val)
            preorder(root.left)
            preorder(root.right)

        res = list()
        preorder(root)
        return res

# 中序遍历
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        def inorder(root: TreeNode):
            if not root:
                return
            inorder(root.left)
            res.append(root.val)
            inorder(root.right)

        res = list()
        inorder(root)
        return res

# 后序遍历
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        def postorder(root: TreeNode):
            if not root:
                return
            postorder(root.left)
            postorder(root.right)
            res.append(root.val)

        res = list()
        postorder(root)
        return res

迭代思路

可以使用栈进行迭代，以前序遍历为例，过程表示如下：

• 初始化栈，将根节点入栈
• 当栈不为空时：
  • 弹出栈顶元素Node，并将值添加到结果中；
  • 如果Node的右子树非空，将右子树入栈
  • 如果Node的左子树非空，将左子树入栈

#前序遍历
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        stack,res=[root],[]
        while stack:
            node=stack.pop()
            if node:
                res.append(node)
                if node.right:
                    stack.append(node.right)
                if node.left:
                    stack.append(node.left)
        return res

# 中序遍历
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        cur,stack,res=root,[],[]
        while stack or cur:
            while cur: #cur入栈，并到达最左端的叶子结点
                stack.append(cur)
                cur=cur.left
            tmp=stack.pop()
            res.append(tmp.val)
            cur=tmp.right
        return res

# 后序遍历
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
        cur,stack,res=root,[],[]
        while stack or cur:
            while cur: #最先到达右端
                res.append(cur.val)
                stack.append(cur)
                cur=cur.right
            tmp=stack.pop()
            cur=tmp.left
        return res[::-1]

层序遍历

层序遍历使用广度优先搜索，步骤为：

• 初始化队列q，并将根节点root加入到队列中
• 当队列不为空时：
  • 计算当前层的元素个数，即队列长度
  • 队列弹出节点node,加入到结果中；
  • 如果左子树非空，左子树加入队列；
  • 如果右子树非空，右子树加入队列。

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []

        queue=deque()
        queue.append(root)

        result=[]
        while queue:
            tmp=[]
            num=len(queue)
            for i in range(num):
                node=queue.popleft()
                tmp.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(tmp)

        return result

Leecode.617 合并二叉树

题目链接：https://leetcode.cn/problems/merge-two-binary-trees/description/

给你两棵二叉树： root1 和 root2 。

想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为null的节点将直接作为新二叉树的节点。

返回合并后的二叉树。

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

示例1：

输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]

解题思路

深度优先搜索

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

在遍历二叉树的各个节点时，一共会出现如下三种情况：

• 两个二叉树的对应节点都为空，则合并后的二叉树的对应节点也为空；
• 两个二叉树的对应节点只有一个为空，则合并后的二叉树的对应节点为其中的非空节点；
• 两个二叉树的对应节点都不为空，则合并后的二叉树的对应节点的值为两个二叉树的对应节点的值之和，此时需要显性合并两个节点。

在一个节点合并完成后，还需要对该节点的左右字数进行相同操作，直至二叉树为空，该过程是一个递归过程。

复杂度分析

时间复杂度：O(min(m,n))，其中m和n分别是两个二叉树的节点个数。
空间复杂度：O(min(m,n))，其中m和n分别是两个二叉树的节点个数。

案例代码

class Solution:
    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:
        #如果有空节点：
        if not t1:
            return t2
        if not t2:
            return t1

        #如果两颗树的节点均不为空，对两节点值进行合并
        Node=TreeNode(t1.val+t2.val)
        #递归，遍历左右节点
        Node.left=mergeTrees(t1.left,t2.left)
        Node.right=mergeTrees(t1.right,t2.right)
        return Node

Leecode.823 带因子的二叉树

题目链接：https://leetcode.cn/problems/binary-trees-with-factors/description/

给出一个含有不重复整数元素的数组 arr，每个整数arr[i]均大于 1。

用这些整数来构建二叉树，每个整数可以使用任意次数。其中：每个非叶结点的值应等于它的两个子结点的值的乘积。

满足条件的二叉树一共有多少个？答案可能很大，返回 对10^9 + 7取余的结果。

示例：

输入：arr=[2,4]
输出：3
解释：可以得到这些二叉树：[2],[4],[4,2,2]

解题思路

动态规划+双指针
题目中每个整数arr[i]都大于1，因此每个非子叶节点的值都大于它子叶节点的值。

• 将arr从小到大进行排序，对于以arr[i]为根节点的带因子的二叉树，它的子孙节点值得下标只能在区间[0,i-1]中。
• 使用dp[i]保存以arr[i]为根节点的带因子的二叉树数目
• 从区间[0,i-1]内枚举arr[i]的子节点，假设存在0<=left<=right\<i，使得arr[left]*arr[right]=arr[i]成立，那么arr[left]和arr[right]可以作为arr[i]的两个子节点。
• arr[left]和arr[right]为根节点的带因子二叉树数目分别为dp[left]和dp[right]
• arr[left]和arr[right]作为arr[i]的两个子节点时，带因子二叉树数目S为：
  • left=right时，s=dp[left]*dp[right]
  • left!=right时，因为两个子节点可以交换，所以s=dp[left]dp[right]2

当arr[i]没有子节点时，对应1个带因子二叉树。因此，状态转移方程为：

$$dp[i]=1+\sum_{(left,right)}dp[left]*dp[right]*(1+f(left,right))$$

其中，left=right时，f(left,right)=0，left \neq right时，f(left,right)=1

复杂度分析

• 时间复杂度：O（n^2）
• 空间复杂度：o（n）

案例代码

class Solution:
    def numFactoredBinaryTrees(self, arr: List[int]) -> int:
        n=len(arr)
        arr=sorted(arr)

        dp=[1]*n
        res,mod=0,10**9+7

        for i in range(n):
            left,right=0,i-1

            while left<=right:
                while right>=left and arr[left]*arr[right]>arr[i]:
                    right-=1
                if right>=left and arr[left]*arr[right]==arr[i]:
                    #如果两个节点不相等，可以左右交换，因此二叉树数目*2
                    if right!=left:
                        dp[i]=(dp[i]+dp[left]*dp[right]*2)%mod
                    #相等时不能交换
                    else:
                        dp[i]=(dp[i]+dp[left]*dp[right])%mod
                left+=1
            res=(res+dp[i])%mod
        return res

二叉树的最大深度

题目链接：https://leetcode.cn/problems/er-cha-shu-de-shen-du-lcof/description/
某公司架构以二叉树形式记录，请返回该公司的层级数。

解题思路

二叉树的层序遍历，遍历时对每一层计数

案例代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def calculateDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        queue=[]

        queue.append(root)

        count=0
        while queue:
            temp=queue
            queue=[]
            count+=1
            for i in temp:
                if i.left:
                    queue.append(i.left)
                if i.right:
                    queue.append(i.right)

        return count

Leecode 589. N叉树的前序遍历

题目链接：https://leetcode.cn/problems/n-ary-tree-preorder-traversal/description/
给定一个n叉树的根节点root,返回其节点值的前序遍历
n叉树在输入中按层序遍历进行序列化表示，每组子节点由空值null分隔

解题思路

与二叉树的前序遍历类似，在多叉树中，left节点和right节点被多个child替代，可以使用循环进行遍历。

案例代码

class Solution:
    def preorder(self, root: 'Node') -> List[int]:
        ans = []
        def dfs(node: 'Node'):
            if node is None:
                return
            ans.append(node.val)
            for ch in node.children:
                dfs(ch)
        dfs(root)
        return ans

Leecode 114. 二叉树展开为链表

题目链接：https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/description/?envType=study-plan-v2&envId=top-interview-150
给定一个二叉树的根节点root，将他展开为一个单链表：
展开后的单链表应该同样使用TreeNode，其中right子指针指向链表中下一个结点，而左子指针始终为null。
展开后的单链表应该与二叉树先序遍历顺序相同。

解题思路

将二叉树展开为单链表之后，单链表中的节点顺序几位二叉树的前序遍历访问各节点的顺序，因此，可以对二叉树进行前序遍历，获得各节点被访问到的顺序。

案例代码

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        preorder_list=[]
        def preorder(root):
            if root:
                preorder.append(root)
                preorder(root.left)
                preorder(root.right)

        preorder(root)
        size=len(preorder_list)
        for i in range(1,size):
            prev,curr=preorder_list[i-1],preorder_list[i]
            prev.left=None
            prev.right=curr

也可以使用后序遍历和递归完成解题：

class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """

        def preorder(root):

            if root == None:
                return 

            preorder(root.left)
            preorder(root.right)

            if root.left!=None:
                pre=root.left
                while pre.right:
                    pre=pre.right
                pre.right=root.right
                root.right=root.left
                root.left=None
            root = root.right

        preorder(root)

也可以构造图的方法解题：

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> Optional[TreeNode]:
        # 终止递归条件，树为空
        if not inorder or not postorder:
            return None

        #根节点的值为后序遍历的最后一个元素值
        rootVal = postorder[-1]

        #创建根节点
        root = TreeNode(rootVal)

        #用根节点的值去中序数组中查找对应元素下标
        midIndex=inorder.index(rootVal)

        #找出中序遍历的左子树和右子树
        #左子树区间为[0，midIndex)，右子树的区间为[midIndex+1,n-1]
        inorderLeft=inorder[:midIndex]
        inorderRight=inorder[midIndex+1:]

        #找出后序遍历的左子树和右子树
        #后序遍历和中序遍历的左子树和右子树长度相等，所以可以通过中序遍历的左右子树长度来确定后序遍历左右子树的位置
        postorderLeft = postorder[:len(inorderLeft)]
        postorderRight=postorder[len(inorderLeft):len(inorder)-1]

        # 递归遍历左子树
        root.left=self.buildTree(inorderLeft,postorderLeft)
        # 递归遍历右子树
        root.right=self.buildTree(inorderRight,postorderRight)

        return root