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

前序、中序、后序指的是根输出的顺序
1.递归遍历
前序遍历：打印 -> 左 -> 右
中序遍历：左 -> 打印 -> 右
后序遍历：左 -> 右 -> 打印

1.1递归前序遍历
from typing import List
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        path = []
        def dfs(tree_node):
            if not tree_node:
                return
            path.append(tree_node.val)
            dfs(tree_node.left)
            dfs(tree_node.right)

        dfs(root)
        return path

1.2递归中序遍历
终止条件：当前节点为空
函数内：递归的调用左节点，打印当前节点，再递归调用右节点
时间复杂度：O(n)
空间复杂度：O(h),h是树的高度

from typing import List
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        path = []
        def dfs(tree_node):
            if not tree_node:
                return
            dfs(tree_node.left)
            path.append(tree_node.val)
            dfs(tree_node.right)

        dfs(root)
        return path

1.3递归后序遍历

from typing import List
class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        path = []
        def dfs(tree_node):
            if not tree_node:
                return
            dfs(tree_node.left)
            dfs(tree_node.right)
            path.append(tree_node.val)

        dfs(root)
        return path


2. 栈 + 迭代

递归实现时，是函数自己调用自己，一层层的嵌套下去，操作系统/虚拟机自动帮我们用栈来保存了每个调用的函数，现在我们需要自己模拟这样的调用过程
#栈 ,先进后出
# 前序遍历，出栈顺序:根左右
# 中序遍历，出栈顺序:左根右
# 后序遍历，出栈顺序:左右根

2.1迭代前序遍历

2.1.1模拟递归迭代过程的编码方式

from typing import List
class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        ans = []
        stack = []
        while stack or root:
            if root:
                ans.append(root.val)
                stack.append(root)
                root = root.left
            else:
                tmp = stack.pop()
                root = tmp.right
        return ans

2.1.2 利用进出栈顺序编程

前序遍历顺序:  中左右
用列表模拟栈： 栈 ->后进先出
故前序遍历     出栈顺序:中左右 入栈顺序:右左中

class Solution:
    def preorderTraversal(self, root: TreeNode) -> List[int]:
        ans = []
        stack = []
        if not root:
            return ans
        stack.append(root)
        while stack:
            tree_node = stack.pop()
        #入栈顺序右左中
            ans.append(tree_node.val)
            if tree_node.right:
                stack.append(tree_node.right)
            if tree_node.left:
                stack.append(tree_node.left)
        return ans

#更好理解的前序迭代
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        #列表模拟栈 ,先进后出
        #前序、中序、后序指的是根输出的顺序
        # 前序遍历，出栈顺序:根左右，入栈顺序：右左根
        ans = []
        stack = []
        if root:
            stack.append(root)
        while stack:
            node = stack.pop()
            if node:
                if node.right:#右
                    stack.append(node.right)
                if node.left:#左
                    stack.append(node.left)
                stack.append(node)#中
                stack.append(None)
            else:
                node = stack.pop()
                ans.append(node.val)
        return ans



2.2 迭代中序遍历

2.2.1 模拟递归迭代过程
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        
        ans = []
        stack = []
        while stack or root:
            # 不断往左子树方向前进，每次前进将当前节点保存到栈中
            # 模拟递归的调用
            if root:
                stack.append(root)
                root = root.left
            #当前节点为空时，说明左边走到头，从栈中弹出节点并保存
            #然后转到右边节点，继续上面的过程
            else:
                tmp = stack.pop()
                ans.append(tmp.val)
                root = tmp.right
        return ans

更好理解的中序迭代
class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        # 中序遍历，出栈顺序:左根右，入栈顺序：右根左
        ans = []
        stack = []
        if root:
            stack.append(root)
        while stack:
            node = stack.pop()
            if node:
                if node.right:#右
                    stack.append(node.right)
                stack.append(node)#中
                stack.append(None)#中节点访问过，但未处理，加入空节点做标记
                if node.left:#左
                    stack.append(node.left)
            else:
                node = stack.pop()
                ans.append(node.val)
        return ans

2.3 迭代后序遍历
   
from collections import deque
from typing import List


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


def make_tree(data):
    if data == []:
        return
    root = TreeNode(data[0])
    queue = deque([root])
    i = 1
    while i < len(data):
        node = queue.popleft()
        if data[i] != ‘null‘:
            node.left = TreeNode(data[i])
            queue.append(node.left)
        i = i + 1
        if data[i] != ‘null‘:
            node.right = TreeNode(data[i])
            queue.append(node.right)
        i = i + 1
    return root


class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
    # 后序遍历，出栈顺序:左右根，入栈顺序：根右左
        ans = []
        stack = []
        if root:
            stack.append(root)
        while stack:
            node = stack.pop()
            if node:
                stack.append(node)#中节点访问过，但未处理，加入空节点做标记
                stack.append(None)
                if node.right:
                    stack.append(node.right)#右
                if node.left:
                    stack.append(node.left)#左
            else:
                node = stack.pop()
                ans.append(node.val)
        return ans