Inorder Traversal

题目描述

解题方法

  • 递归
  • stack
  • morris

stack

跟preorder不同的是，这里root不是先visit的

  • 我们要用一个cur来保存当前到达的节点（不是记录到result里的节点，而是要Push到stack上的）
  • 因为stack是后进后出的，所以一开始可以先将root加到stack,并且不断地将left child加到stack
  • 只有当curr为None的时候，说明当前已经肯定没有left child，这时候才从stack里pop出来一个加到result数组里, 然后继续往right child走（如果有的话）
  • 如果没有right child, 那么cur还是None，stack又会pop，就又到了上面的node

Morris (google onsite的时候被问到了)

Solution

递归

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        result = []
        self.helper(result, root)
        return result

    def helper(self, result, root):
        if not root:
            return

        self.helper(result, root.left)
        result.append(root.val)
        self.helper(result, root.right)

stack

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if not root:
            return []
        cur = root
        stack = []
        result = []
        while cur or stack:
            if cur:
                stack.append(cur)
                cur = cur.left
            else:
                cur = stack.pop()
                result.append(cur.val)
                cur = cur.right

        return result

Reference