二叉树算法之【前序遍历】

目录

LeetCode-144题

LeetCode-144题

给定二叉树的根节点root，返回它节点值的前序遍历。

class Solution {public List<Integer> preorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();order(root, result);return result;}private void order(TreeNode root, List<Integer> pre) {//当前节点TreeNode curr = root;//借助栈LinkedList<TreeNode> stack = new LinkedList<>();//最近一次pop的元素TreeNode pop = null;while (curr != null || !stack.isEmpty()) {if (curr != null) {stack.push(curr);pre.add(curr.val);//待处理左节点curr = curr.left;} else {//栈不为空TreeNode peek = stack.peek();//右节点为空if (peek.right == null) {pop = stack.pop();}//右节点处理完else if (peek.right == pop) {pop = stack.pop();}//处理右节点else {curr = peek.right;}}}}
}