144. 二叉树的前序遍历

题目描述

原题

给定一个二叉树,返回它的 前序 遍历。

示例:

输入: [1,null,2,3]
1
\
2
/
3
输出: [1,2,3]

进阶: 递归算法很简单,你可以通过迭代算法完成吗?

题解

Java
Kotlin
Java
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root != null){
list.add(root.val);
list.addAll(preorderTraversal(root.left));
list.addAll(preorderTraversal(root.right));
}
return list;
}
}
Kotlin
class Solution {
fun preorderTraversal(root: TreeNode?): List<Int> {
val list = ArrayList<Int>()
if(root != null){
//注意加引号
list.add(root.`val`)
list.addAll(preorderTraversal(root.left))
list.addAll(preorderTraversal(root.right))
}
return list
}
}

迭代

class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null){
return list;
}
LinkedList<TreeNode> stack = new LinkedList();
stack.push(root);
while(!stack.isEmpty()){
root = stack.pop();
list.add(root.val);
if(root.right!=null){
stack.push(root.right);
}
if(root.left!=null){
stack.push(root.left);
}
}
return list;
}
}