题目描述

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

示例:
```
输入: [1,null,2,3]
   1
    \
     2
    /
   3
  
输出: [1,3,2]
```
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

我的解法1——递归（AC）

递归中序遍历
时间复杂度O(n)，空间复杂度O(n)
Beat 96%

# 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 __init__(self):
        self.res = []
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        if(root is None):
            return self.res
        self.inorderTraversal(root.left)
        self.res.append(root.val)
        self.inorderTraversal(root.right)
        return self.res

我的解法2——非递归

非递归中序遍历，用到了栈
时间复杂度O(n)，空间复杂度O(n)
Beat 10%

# 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 inOrNot(self, stack, root):
        while(root):
            stack.append(root)
            root = root.left
        return stack
        
    def inorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        res = []
        stack = []
        
        stack = self.inOrNot(stack, root)
        
        while(len(stack) != 0):
            for item in stack:
                print(item.val)
            
            if(stack[len(stack) - 1].right is not None):
                temp = stack[len(stack) - 1].right
                res.append(stack[len(stack) - 1].val)
                stack = stack[:len(stack) - 1]
                stack = self.inOrNot(stack, temp)
            else:
                res.append(stack[len(stack) - 1].val)
                stack = stack[:len(stack) - 1]
        
        return res

参考答案

https://leetcode.com/problems/binary-tree-inorder-traversal/solution/