题目


144.二叉树的前序遍历

145.二叉树的后序遍历

94.二叉树的中序遍历
 

给你二叉树的根节点 root ,返回它节点值的 前序 遍历。

示例 1:

输入:root = [1,null,2,3]

输出:[1,2,3]

解释:

示例 2:

输入:root = [1,2,3,4,5,null,8,null,null,6,7,9]

输出:[1,2,4,5,6,7,3,8,9]

解释:

示例 3:

输入:root = []

输出:[]

示例 4:

输入:root = [1]

输出:[1]

思路

前序遍历(迭代法)

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

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

后序遍历(迭代法)

先序遍历是中左右,后序遍历是左右中,那么我们只需要调整一下先序遍历的代码顺序,就变成中右左的遍历顺序,然后在反转result数组,输出的结果顺序就是左右中了,如下图:

中序遍历(迭代法)

在遍历过程中有两个操作:

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

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

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

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

代码

前序遍历

# 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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        nums = []
        stack = [root]
        while stack:
            temp = stack.pop()
            nums.append(temp.val)
            if temp.right:
                stack.append(temp.right)
            if temp.left:
                stack.append(temp.left)
        return nums

后序遍历

# 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 postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root:
            return []
        nums = []
        stack = [root]
        while stack:
            temp = stack.pop()
            nums.append(temp.val)
            if temp.left:
                stack.append(temp.left)
            if temp.right:
                stack.append(temp.right)
        return nums[::-1]

中序遍历

# 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 inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if not root :
            return []

        stack =[]
        result = []
        cur = root
        while cur or stack:#cur或者stack中有一个不为空,都一直继续
            if cur:#如果当前节点不为空的时候,就将当前节点指向该节点的左子树
                stack.append(cur)
                cur = cur.left
            else:#如果当前节点为空,那就需要从stack中取出最后一个节点,中序遍历,这个就是中间那个数,再指向右子树
                cur = stack.pop()
                result.append(cur.val)
                cur = cur.right
        return result

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部