力扣 144. 二叉树的前序遍历
题目描述
给定一个二叉树，返回它的前序遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [1,2,3]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？
递归版前序遍历
# 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 preorderTraversal(self, root: TreeNode) -> List[int]:
res = []
def preorder(node):
if node is None:
return
res.append(node.val)
preorder(node.left)
preorder(node.right)
return preorder(root) or res
运行结果：
❝执行结果：通过
执行用时：48 ms, 在所有 Python3 提交中击败了17.69% 的用户
内存消耗：13.6 MB, 在所有 Python3 提交中击败了5.01% 的用户
递归版一行解
最爱的力扣一行解系列。
# 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 preorderTraversal(self, root: TreeNode) -> List[int]:
return [root.val] + self.preorderTraversal(root.left) + self.preorderTraversal(root.right) if root else []
运行结果：
❝执行结果：通过
执行用时：28 ms, 在所有 Python3 提交中击败了99.15% 的用户
内存消耗：13.5 MB, 在所有 Python3 提交中击败了5.01% 的用户
迭代版前序遍历
这里用到了类型区分法，只要掌握了这种方法，二叉树迭代遍历就如砍瓜切菜般简单，它是颜色标记法的改良版。
# 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 preorderTraversal(self, root: TreeNode) -> List[int]:
res, q = [], [root]
while q:
node = q.pop()
if isinstance(node, TreeNode):
q.extend([node.right, node.left, node.val])
elif isinstance(node, int):
res.append(node)
return res
运行结果：
❝执行结果：通过
执行用时：36 ms, 在所有 Python3 提交中击败了87.61% 的用户
内存消耗：13.6 MB, 在所有 Python3 提交中击败了5.01% 的用户
2020.10.27