二叉樹中序周遊_二叉樹的中序周遊

來源：https://www.cnblogs.com/zuoyuan/p/3720273.html

說明：最近兩周一直在寫跟二叉樹有關的業務代碼，找到一個比較詳細的中序周遊說明，版權歸原作者所有，侵删。原作者：

南郭子綦 另，作者部落格上打了leetcode标簽的文章有155篇，打算刷leetcode可以參考。

補充：業務邏輯稍微複雜一點，iterative_inorder函數裡面就要用狀态機了，否則根本區分不出來目前是左、右、還是root。比如拼接字元串的時候。

原題位址：http://oj.leetcode.com/problems/binary-tree-inorder-traversal/
題意：二叉樹的中序周遊。這道題用遞歸比較簡單，考察的是非遞歸實作二叉樹中序周遊。中序周遊順序為：左子樹，根，右子樹。如此遞歸下去。
解題思路：假設樹為：
                                1
　　　　　　　　　　　　　　　/　  
　　　　　　　　　　　　　　 2　　  3
　　　　　　　　　　　　　  /   　 /   
   　　　　　　　　　　　　4     5  6    7
我們使用一個棧來解決問題。步驟如下：
　　　　一，我們将根節點1入棧，如果有左孩子，依次入棧，那麼入棧順序為：1，2，4。由于4的
左子樹為空，停止入棧，此時棧為{1，2，4}。
　　　　二，此時将4出棧，并周遊4，由于4也沒有右孩子，那麼根據中序周遊的規則，我們顯然應
該繼續周遊4的父親2，情況是這樣。是以我們繼續将2出棧并周遊2，2存在右孩子，将5入棧，此時
棧為{1，5}。
　　　　三，5沒有孩子，則将5出棧并周遊5，這也符合中序周遊的規則。此時棧為{1}。
　　　　四，1有右孩子，則将1出棧并周遊1，然後将右孩子3入棧，并繼續以上三個步驟即可。
　　　　棧的變化過程：{1}->{1,2}->{1,2,4}->{1,2}->{1}->{1,5}->{1}->{}->{3}->{3,6}->{3}->
{}->{7}->{}。

代碼：


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

class Solution:
    # @param root, a tree node
    # @return a list of integers
    def iterative_inorder(self, root, list):
        stack = []
        while root or stack:
            if root:
                stack.append(root)
                root = root.left
            else:
                root = stack.pop()
                list.append(root.val)
                root = root.right
        return list
 
    def recursive_inorder(self, root, list):
        if root:
            self.inorder(root.left, list)
            list.append(root.val)
            self.inorder(root.right, list)
 
    def inorderTraversal(self, root):
        list = []
        self.iterative_inorder(root, list)
        return list