【LeetCode】144. 二叉树的前序遍历（Java）

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

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

解法一

递归，简单写法，解法二为迭代。

/** * 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 { private List<Integer> res = new ArrayList<>(); public List<Integer> preorderTraversal(TreeNode root) { if (root == null) return res; //前序遍历 res.add(root.val); preorderTraversal(root.left); preorderTraversal(root.right); return res; } }

解法二

迭代

class Solution { public List<Integer> preorderTraversal(TreeNode root) { //迭代 List<Integer> res = new ArrayList<>(); //特判 if (root == null) return res; //栈 Deque<TreeNode> stack = new ArrayDeque<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode temp = stack.pop(); //把当前值存入res中 res.add(temp.val); //如果当前节点的右节点不为空，就放到栈中（先放右节点，再放左节点） if (temp.right != null) stack.push(temp.right); //如果当前节点的左节点不为空，就放到栈中 if (temp.left != null) stack.push(temp.left); } return res; } }