94：二叉树的中序遍历

问题描述

给定一个二叉树，返回它的中序 遍历。

示例：

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

输出: [1,3,2]

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

问题分析

递归的话，标准的二叉树的中序遍历即可。
非递归的话，用stack来解决。对于每一个结点，如果它有左孩子，就压栈，没有左孩子就弹栈，然后压入它的右孩子。然后来循环的解决问题。
需要考虑的点是，我们对于每个新加入的结点都要先找左子树，再弹栈，再找右子树。那么怎么判断当前点是从栈里弹出来的还是怎么样呢？如果是从栈里弹出来的，那就不能再去找左子树了，不然就死循环在这里了，所以我加了个stack_flag来表示是弹栈的点还是新加入的点。

递归代码：

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

class Solution:
    def inorderTraversal(self, root):
        res = []
        def solution(root):
            if not root:
                return
            solution(root.left)
            res.append(root.val)
            solution(root.right)
        solution(root)
        return res

非递归代码：

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

class Solution:
    def inorderTraversal(self, root):
        res = []
        if not root:
            return res
        stack = [root]
        flag = False # 标记是回退的还是新增的
        while len(stack):
            top = stack[-1]
            while not flag and top.left: # 左子树压栈
                stack.append(top.left)
                top = top.left
            res.append(top.val)
            stack.pop() # 压不下去了就弹栈
            flag = True # 证明是弹栈得来的
            if top.right:
                stack.append(top.right) # 新的压栈
                flag = False # 证明是压栈的
        return res

    def test(self):
        t1 = TreeNode(1)
        t1.left = None
        t1.right = TreeNode(2)
        t1.right.left = TreeNode(3)
        print(self.inorderTraversal(t1))

s = Solution()
s.test()