leetcode94 -- Binary Tree Inorder Traversal (二叉树中序遍历)

# 小郑之家~

### 题目

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

Example:

Input: [1,null,2,3]
1
\
2
/
3

Output: [1,3,2]



### 法一，递归

class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
res = []
self.inorder(root, res)
return res

def inorder(self,root,res):
if not root:
return
if root.left:
self.inorder(root.left,res)
res.append(root.val)
if root.right:
self.inorder(root.right, 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: TreeNode) -> List[int]:
res = []

stack = []
p = root
while p or len(stack)>0:
while p:
stack.append(p)
p = p.left

p = stack.pop()
res.append(p.val)
p = p.right

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: TreeNode) -> List[int]:
res = []

stack = []
p = root
while p or len(stack)>0:
if p:
stack.append(p)
p = p.left
else:
p = stack.pop()
res.append(p.val)
p = p.right
return res