leetcode_深度搜索和广度搜索 94. 二叉树的中序遍历

94. 二叉树的中序遍历

• 给定一个二叉树的根节点root ，返回它的中序遍历 。
• 中序遍历顺序为: 左 ——根——右

递归遍历

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: List[int]
        """
        result = [] 
        
        def inorder(node):
            if node is None:
                return []
            inorder(node.left)
            result.append(node.val)
            inorder(node.right)
        
        inorder(root)
        return result

• 时间复杂度: O(n)
• 空间复杂度: O(log n) ~ O(n) , 其中O(log n)为完全二叉树的情况; 或O(h), h是树的高度

非递归遍历(栈)

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: List[int]
        """
        result, stack = [], []
        cur = root
        
        while crr or stack:
            while cur:
                stack.append(cur)
                cur = cur.left  # 遍历左子树
            
            cur = stack.pop()
            result.append(cur.val)  # 访问当前节点
            
            cur = cur.right  # 遍历右子树
        
        return result

• 时间复杂度: O(n)
• 空间复杂度: O(h), h是树的高度