给你二叉树的根节点 root ，返回它节点值的前序 遍历。
输入：root = [1,null,2,3]输出：[1,2,3]
输入：root = []输出：[]
输入：root = [1]输出：[1]
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
// 递归算法实现遍历
class Solution {
List<Integer> treeList = new ArrayList<Integer>();
public List<Integer> preorderTraversal(TreeNode root) {
TreeNode cur = root;
if (cur == null) {
return treeList;
}
treeList.add(cur.val);
if (cur.left != null) {
preorderTraversal(cur.left);
}
if (cur.right != null) {
preorderTraversal(cur.right);
}
return treeList;
}
}
代码简化如下：
class Solution {
private List<Integer> preorder(TreeNode node, List<Integer> list) {
if (node == null) {
return list;
}
list.add(node.val);
preorder(node.left, list);
preorder(node.right, list);
return list;
}
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
return preorder(root, list);
}
}
// 迭代方法
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
if (root == null) {
return list;
}
Deque<TreeNode> stack = new LinkedList<>();
TreeNode node = root;
while (!stack.isEmpty() || node != null) {
while (node != null) {
list.add(node.val);
stack.push(node);
node = node.left;
}
node = stack.pop();
node = node.right;
}
return list;
}
}
网友评论