二叉树的前序遍历
题目描述
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：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 {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
preOrder(ans, root);
return ans;
}
private void preOrder(List<Integer> ans, TreeNode root) {
if (root!=null) {
ans.add(root.val);
preOrder(ans, root.left);
preOrder(ans, root.right);
}
}
}
方法二：迭代
我们也可以用迭代的方式实现方法一的递归函数，两种方式是等价的，区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来，其余的实现与细节都相同，具体可以参考下面的代码。
思路：针对二叉树先序遍历 根->左子树->右子树 的顺序
- 对于每一个结点，我们一直遍历到它的最左边
- 然后返回上一个结点
- 再遍历它的右边。
/**
* 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 {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> ans = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
while (root!=null || !stack.isEmpty()) {
while (root!=null) {
ans.add(root.val);
stack.add(root);
root = root.left;
}
root = stack.pop();
root = root.right;
}
return ans;
}
}
方法三：Morris 遍历
Morris 遍历的核心思想是利用树的大量空闲指针，实现空间开销的极限缩减。其前序遍历规则总结如下：
- 新建临时节点，令该节点为
root； - 如果当前节点的左子节点为空，将当前节点加入答案，并遍历当前节点的右子节点；
- 如果当前节点的左子节点不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点：
- 如果前驱节点的右子节点为空，将前驱节点的右子节点设置为当前节点。然后将当前节点加入答案，并将前驱节点的右子节点更新为当前节点。当前节点更新为当前节点的左子节点。
- 如果前驱节点的右子节点为当前节点，将它的右子节点重新设为空。当前节点更新为当前节点的右子节点。
- 重复步骤 2 和步骤 3，直到遍历结束。
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<Integer>();
if (root == null) {
return res;
}
TreeNode p1 = root, p2 = null;
while (p1 != null) {
p2 = p1.left;
if (p2 != null) {
while (p2.right != null && p2.right != p1) {
p2 = p2.right;
}
if (p2.right == null) {
res.add(p1.val);
p2.right = p1;
p1 = p1.left;
continue;
} else {
p2.right = null;
}
} else {
res.add(p1.val);
}
p1 = p1.right;
}
return res;
}
}