题目描述
题目链接:144. Binary Tree Preorder Traversal
Given the
root
of a binary tree, return the preorder traversal of its nodes‘ values.
例子
例子 1
Input: root = [1,null,2,3]
Output: [1,2,3]
例子 2
Input: root = []
Output: []
例子 3
Input: root = [1]
Output: [1]
例子 4
Input: root = [1,2]
Output: [1,2]
例子 5
Input: root = [1,null,2]
Output: [1,2]
Constraints
The number of nodes in the tree is in the range
[0, 100]
.-100 <= Node.val <= 100
Follow Up
Recursive solution is trivial, could you do it iteratively?
解题思路
递归的方法比较容易,这里放一个迭代版本,用栈可以实现类似的效果。如果我们始终往往栈中先放入右子树再放入左子树,每次取栈顶节点的值放入结果中。这样就会优先处理左子树,因此可以以preorder
的顺序输出值,代码如下:
1 | /** |
- 时间复杂度: O(n)
- 空间复杂度: O(h)
GitHub 代码同步地址: 144.BinaryTreePreorderTraversal.cpp
其他题目:
GitHub: Leetcode-C++-Solution
博客: Leetcode-Solutions