94. Binary Tree Inorder Traversal

94. Binary Tree Inorder Traversal (Easy) 二叉树的中序遍历

题干

Given the root of a binary tree, return the inorder traversal of its nodes’ values.

Example 1:

Input: root = [1,null,2,3]
Output: [1,3,2]

Example 2:

Input: root = []
Output: []

Example 3:

Input: root = [1]
Output: [1]

Constraints:

• The number of nodes in the tree is in the range [0, 100].
• -100 <= Node.val <= 100

Follow up: Recursive solution is trivial, could you do it iteratively?

解法

递归解法

中序遍历，就是左中右这种顺序

• 输入参数：node节点，保存结果的列表
• 输出参数：空
• 结束条件：当node是None的时候直接返回
• 单层关键逻辑：当node不是None的时候，先处理左节点（需递归），将结果加入到结果，然后是中节点（当前节点，无需递归），然后时右节点（需递归）。

# 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]:
        res = []
        self.traversal(root, res)
        return res
    
    def traversal(self, node: Optional[TreeNode], res: List[int]):
        if node is None:
            return
        
        self.traversal(node.left, res)
        res.append(node.val)
        self.traversal(node.right, res)

栈解法

中序遍历，就是左中右顺序。

• 栈中保存需要后序处理的节点（当前节点的左子树上所有的左节点），直到当前节点为None
• 从栈中弹出元素，记录当前元素的值，然后使用当前节点的right节点当作当前节点，进入下次循环

# 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]:
        answer: List[int] = []
        st_node: List[int] = []
        cur_node = root

        # 中序遍历：左中右
        # 左子树依序入栈，到底后逐个弹出，处理中和右
        while cur_node or st_node:
            # 先处理当前节点的左子树
            while cur_node:
                st_node.append(cur_node)
                cur_node = cur_node.left

            # 将栈顶元素弹出栈（左节点首先会在栈顶）
            cur_node = st_node.pop()
            answer.append(cur_node.val)

            # 若无right，cur_node为None，会在下个循环中重新pop一个
            cur_node = cur_node.right
        
        return answer