94. 二叉树的中序遍历

给定一个二叉树的根节点 root ，返回它的 中序 遍历。
示例 1：
94. 二叉树的中序遍历 - 图1

  1. 输入：root = [1,null,2,3]
  2. 输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

示例 4：
94. 二叉树的中序遍历 - 图2

输入：root = [1,2]
输出：[2,1]

示例 5：
94. 二叉树的中序遍历 - 图3

输入：root = [1,null,2]
输出：[1,2]

提示：

  • 树中节点数目在范围 [0, 100] 内
  • 100 <= Node.val <= 100

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

递归解法

# 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]:
        L=[]
        def dfs(root):
            if root.left:
                dfs(root.left)
            L.append(root.val)
            if root.right:
                dfs(root.right)
        if root:
            dfs(root)
        return L

Untitled.png

迭代算法

这是第一种写法，比较丑陋，如果有左节点，就将其存入栈中，然后访问左子树；
如果没有左节点了，就访问根节点，然后访问右子树。
要用一个flag判断是否左节点已经被访问过。

class Solution:
    def inorderTraversal(self, root: TreeNode) -> List[int]:
        Stack=[]
        L=[]
        if not root:
            return []
        Stack.append(root)
        flag=False
        while Stack:
            i=Stack[-1]
            if flag:
                flag=False
            elif i.left:
                Stack.append(i.left)
                continue
            L.append(i.val)
            Stack.pop()
            if i.right:
                Stack.append(i.right)
                continue
            flag=True
        return L

也有一种更简洁的，但是理解起来更难：

  1. 如果当前节点非空，将节点压入栈，移动到左节点
  2. 如果当前节点为空，从栈中取出一个元素作为当前节点
    1. 访问当前节点
    2. 移动到右节点
      class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
  Stack = []
  L = []
  while root or Stack:
      while root:
          Stack.append(root)
          root = root.left
      root = Stack.pop()
      L.append(root.val)
      root = root.right
  return L
      Untitled.png