题目:
给你二叉树的根节点
root
,返回它节点值的 前序 遍历。来源:力扣(LeetCode)
链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台
示例:
示例 1:
输入:root = [1,null,2,3]
输出:[1,2,3]
示例 2:输入:root = []
输出:[]
示例 3:输入:root = [1]
输出:[1]示例4:
输入:root = [1,2]
输出:[1,2]
示例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 preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:result = []stack = [root]while root and stack:root = stack.pop()result.append(root.val)if root.right:stack.append(root.right)if root.left:stack.append(root.left)return result