原題
給出一棵二叉樹,返回其中序遍歷
給出二叉樹 {1,#,2,3}
1
\
2
/
3
返回 [1,3,2]
解題思路
- 方法一：遞歸，定義helper函數(shù)
- 方法二：Divide & Conquer
- 方法二：非遞歸
- (操作一)每一次從當前節(jié)點開始(第一次是root節(jié)點)遍歷至最左節(jié)點，一次入棧。
- (操作二)pop出棧一個node蛤育，node.val加入到結(jié)果，然后看該node有沒有右兒子
- 有的話重復操作一
- 沒有的話，繼續(xù)pop出棧一個node次乓，重復操作二
- 非遞歸解法可以體會一下另外一個題[Inorder Successor in Binary Search Tree]
完整代碼
# 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 inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
res = []
self.helper(root, res)
return res
def helper(self, root, result):
if root != None:
self.helper(root.left, result)
result.append(root.val)
self.helper(root.right, result)
# 方法二
class Solution(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
result = []
if root == None:
return result
result.append(root.val)
# divide
left = self.inorderTraversal(root.left)
right = self.inorderTraversal(root.right)
# conquer
return left + result + right
# 方法三
class Solution(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
stack = []
result = []
current = root
while current != None or len(stack) != 0:
while current != None:
stack.append(current)
current = current.left
current = stack[-1];
stack.pop();
result.append(current.val);
current = current.right;
return result
