Day9——二叉树遍历1

打卡题目：leetcode第94题，二叉树的中序遍历
相似题目：144、145
注意：一定要掌握二叉树最常见的遍历方式，一定要明确前序、中序、后序（这里的前中后指的是根节点的遍历顺序）。除了递归方法，最好再理解和掌握非递归方法。

【思路】
前序遍历、中序遍历、后序遍历，这三种遍历方式中，前中后指的都是根节点的顺序，并且都是先遍历左子树、再遍历右子树。

• 中序遍历递归解法：先递归遍历左子树，再访问当前节点的值，最后递归遍历右子树。
• 中序遍历非递归解法：
  • 使用两个栈，一个栈（栈1）存储节点，另一个栈（栈2）存储访问标签。要想实现左根右的顺序，则需要先插入右节点，再插入根节点，最后插入左节点
  • 实现步骤为：如果栈1的栈顶节点没被访问，则弹出该节点，并将右孩子节点（若有）加入栈中，将该节点加入栈，最后将左孩子节点（若有）加入栈中；同时栈2加入对应的是否被访问的标签。

【代码】

• 递归解法

  # 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 traverse(self, node):
        if not node:
            return
        # 左根右
        self.traverse(node.left)
        self.res.append(node.val)
        self.traverse(node.right)
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        self.res = []
        self.traverse(root)
        return self.res

• 非递归解法

  # 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: TreeNode) -> List[int]:
        '''非递归遍历'''
        if not root:
            return []
        stack = [root]
        visit = [0]
        res = []
        while len(stack) > 0:
            # 已经遍历过，将val放到res中
            if visit[-1] == 1:
                res.append(stack.pop().val)
                visit.pop()
            # 未遍历过，则遍历左右节点（由于是栈，先保存右节点，再保存左节点）
            else:
                node.stack.pop()
                visit_i = visit.pop()
                if node.right:
                    stack.append(node.right)
                    visit.append(0)
                stack.append(node)
                visit.append(1)
                if node.left:
                    stack.append(node.left)
                    visit.append(0)
        return res