【LeetCode】94. 二叉樹中序周遊

問題描述

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

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

給定一個二叉樹，傳回其節點值的順序周遊。

後續工作:遞歸解決方案很簡單，可以疊代地解決嗎?

輸入: [1,null,2,3]
   1
    \
     2
    /
   3

輸出: [1,3,2]
           

Python 實作

實作一：遞歸。由于遞歸調用對記憶體的使用較多，容易造成棧溢出，實際應用中不建議使用。

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        
        # Recursively.
        ret = []
        
        if root == None:
            return []
        
        if root.left != None:
            ret += self.inorderTraversal(root.left)
        
        ret.append(root.val)
        
        if root.right != None:
            ret += self.inorderTraversal(root.right)
        
        return ret
           

實作二：疊代。這裡使用棧的資料結構來實作，實際上實作的也是一個DFS的過程，将子樹的根節點入棧，周遊至左子樹根節點為空時，出棧傳回上一個根節點，再從右子樹根節點重複上述操作即可。

class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """

        # Iteratively.
        stack, ret, cur = [], [], root
        while True:
            if cur != None:
                # Push the middle root node.
                stack.append(cur)
                cur = cur.left
            elif len(stack) > 0:
                # Pop the middle root node and record its value.
                cur = stack.pop()
                ret.append(cur.val)
                cur = cur.right
            else:
                break
        return ret
           

連結：https://leetcode.com/problems/binary-tree-inorder-traversal/