43. Leetcode 94. 二叉树的中序遍历 (二叉树-二叉树遍历)
程序员文章站
2022-05-20 11:21:19
...
给定一个二叉树的根节点 root ,返回它的 中序 遍历。
示例 1:
输入:root = [1,null,2,3]
输出:[1,3,2]
示例 2:
输入:root = []
输出:[]
示例 3:
输入:root = [1]
输出:[1]
示例 4:
输入:root = [1,2]
输出:[2,1]
示例 5:
输入:root = [1,null,2]
输出:[1,2]
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
# 方法一 递归
if root == None:
return []
output = []
output += self.inorderTraversal(root.left)
output.append(root.val)
output += self.inorderTraversal(root.right)
return output
# 方法二 迭代
if root == None:
return []
stack = []
output = []
p_node = root
while stack or p_node:
while p_node:
stack.append(p_node)
p_node = p_node.left
cur_node = stack.pop()
output.append(cur_node.val)
if cur_node.right:
p_node = cur_node.right
return output
# 方法三 颜色标记法
if root == None:
return []
WHITE, GARY = 0, 1
stack = [(WHITE, root)]
output = []
while stack:
color, root = stack.pop()
if root != None:
if color == WHITE:
stack.append((WHITE, root.right))
stack.append((GARY, root))
stack.append((WHITE, root.left))
else:
output.append(root.val)
return output
上一篇: 113. 路径总和 II
下一篇: 94二叉树的中序遍历