题目

分析

直接递归中序遍历是非常简单的了，本文给出使用栈+while循环的方法来解这道题。

代码

# 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 = []
        stack = []
        if not root :
            return res        
        while(root or len(stack)): # 如果栈中还有元素                        
            while(root): # 如果有左子树
                stack.append(root)
                root = root.left
            
            root = stack[-1]
            stack.pop()
            res.append(root.val)
            
            # 即使right为空，也要测一下
            root = root.right
        return res