打卡群刷题总结0804——二叉树的中序遍历
题目：94. 二叉树的中序遍历
链接：https://leetcode-cn.com/problems/binary-tree-inorder-traversal
给定一个二叉树，返回它的中序 遍历。 示例: 输入: [1,null,2,3] 1 \ 2 / 3 输出: [1,3,2] 进阶: 递归算法很简单，你可以通过迭代算法完成吗？
解题：
1、中序遍历：左根右！
递归解法非常简单：递归遍历左子树，添加该节点，递归遍历右子树。
非递归解法，需要使用栈结构，同时使用一个visit数组标识该节点是否访问过其孩子节点。得到visit栈顶元素，判断是否访问过；如果访问过，则val加入到结果中；否则，右孩子插入到栈顶元素前一个位置，左孩子插入到最后。
代码：
1、递归解法
class Solution(object):
def inorder(self, node):
if not node:
return
self.inorder(node.left)
self.res.append(node.val)
self.inorder(node.right)
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
self.res = []
self.inorder(root)
return self.res
2、非递归解法
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def inorderTraversal(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if not root:
return []
res = []
nodes = [root]
visit = [False]
while len(nodes) > 0:
# 未曾遍历
if not visit[-1]:
# 添加右孩子
parent = nodes[-1]
visit[-1] = True
if parent.right:
parent = nodes.pop()
visit_pa = visit.pop()
nodes.append(parent.right)
visit.append(False)
nodes.append(parent)
visit.append(visit_pa)
# 添加左孩子
if parent.left:
nodes.append(parent.left)
visit.append(False)
# 遍历过
else:
res.append(nodes.pop().val)
visit.pop()
return res
PS：刷了打卡群的题，再刷另一道题，并且总结，确实耗费很多时间。如果时间不够，以后的更新会总结打卡群的题。
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-08-05，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录