[LeetCode]题解（python）：094 Binary Tree Inorder Traversal

题目来源

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

iven a binary tree, return the inorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].

题意分析

Input:tree

Output: inorder traversal

Conditions:中序遍历，要非递归

题目思路

非递归实现

AC代码（Python）

 # 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