二叉树-前中后遍历

Posted on

题干： 返回二叉树的前中后序结果 同时写出递归和非递归的写法

递归的写法还是很好想的 简单而且容易理解
但是用栈来实现二叉树的非递归遍历写法就不是那么好理解
特别是中序遍历

先讨论递归的写法

前中后序的递归的写法不同点就是交换那三条语句的顺序 很简单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 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]:
        res=[]
        
        def dfs(node):
            if node == None:
                return 
           	res.append(node.val)  # 中
        dfs(node.left)        # 左
        dfs(node,right)       # 右
        dfs(root)
        return res

非递归写法

非递归的就有点难度了 我们需要通过栈这个数据结构来实现

前序遍历的非递归遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
      	if not root:
            return []
        stk=[root]
        res=[]
        while stk:
            node = stk.pop()
            res.append(node.val)
            if node.right:
                stk.append(node.right)
            if node.left:
                stk.append(node.left)
        return res

特别需要注意的地方就是 左右节点的入栈顺序 先右节点后左节点！！

按道理前序遍历的顺序是中左右 为什么不是先左节点后右节点呢？

因为栈的特殊性 先进后出 为了确保出栈的顺序正确 进栈的时候就要反着来 先右节点后左节点

后序遍历的非递归遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        if not root:
            return []
       	stk=[root]
        res=[]
        
        while stk:
            node=stk.pop()
            res.append(node.val)
            if node.left:
                stk.append(node.left)
            if node.right:
                stk.append(node.right)
        return res[::-1]

和前序非递归遍历的代码很像 区别在于调换左右节点进栈顺序 然后最后res数组反转一下

其实这里为什么可以这样我也不是很理解 卡尔的解释如下

前序非递归遍历的结果是 中左右 那我们调换一下入栈的顺序 就是 中右左 最后翻转数组 就是目标的左右中！

其实还是可以理解 只是没想到是这么sao的做法

中序非递归遍历

中序是需要单独领出来说的 他和前后代码的结构上有很大的不同

由于中序遍历是左中右 首先要一直找到最左端的节点 一旦到头了 再弹出一个节点并存储答案 然后才是右节点

理解了这段话再看代码就会好很多很多

还有个需要注意的就是 中序遍历需要指针的帮助

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# 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 [] 
        
        res=[]
        stk=[]
        cur=root
        while cur or stk:    # 注意这里的边界情况是or！
            if cur :
                stk.append(cur)
                cur=cur.left
            else :
                cur =stk.pop()
                res.append(cur.val)
                cur=cur.right
        return res