递归法实现前.中.后序遍历
代码随想录 (programmercarl.com)
解题思路
前序遍历：头->左->右
中序遍历：左->头->右
后序遍历：左->右->头
递归法实现流程：1.定义递归函数；2.寻找递归终止条件；3.设计单层递归模块
class Solution():
def __init__(self,val=0,left=None,right=None):
self.val = val
self.left = left
self.right = right
def first_loop(self,head,vec): # 前序遍历
if head is None:
return
vec.append(head.val)
first_loop(head.left,vec)
first_loop(head.right,vec)
return vec
def mid_loop(self,head,vec): # 中序遍历
if head is None:
return
mid_loop(head.left,vec)
vec.append(head.val)
mid_loop(head.right,vec)
return vec
def last_loop(self,head,vec): # 后序遍历
if head is None:
return
last_loop(head.left,vec)
last_loop(head.right,vec)
vec.append(head.val)
return vec
迭代法实现前.中.后序遍历
代码随想录 (programmercarl.com)
解题思路
栈：先将头节点压入空栈，当栈不为空时，执行遍历操作
class Solution():
def __init__(self,val=0,left=None,right=None):
self.val = val
self.left = left
self.right = right
def fist_loop(self,head,vec): # 前序遍历-迭代法
if not head:
return []
stack = [head.val]
while stack:
a = stack.pop()
vec.append(a)
if head.right:
stack.append(head.right)
if head.left:
stack.append(head.left)
return vec
def mid_loop(self,head,vec): # 中序遍历-迭代法
if not head:
return []
stack = []
while head or stack:
if head: # 先进入最左子节点
stack.apppend(head)
head = head.left
else: # 从最左子节点->上一层->右子节点
head = stack.pop()
vec.append(head.val)
head = head.right
return vec
def last_loop(self,head,vec): # 后序遍历-迭代法
if head is None: return []
stack = [head.val]
while stack: # 根据前右左构建vec，再反转vec，即得后序遍历结果
cur = stack.pop()
vec.append(cur.val)
if cur.left:
stack.append(cur.left)
if cur.right:
stack.append(cur.right)
return vec[::-1]