题目

截图自官方

代码

注意官方迭代写法：先序遍历只需先右子节点，再左子节点的顺序将节点压入栈就好。也可以模仿中序遍历的迭代写法。

/** * 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 { // 解法1.递归 // List<Integer> ans=new ArrayList(); // public List<Integer> preorderTraversal(TreeNode root) { // if(root!=null){ // ans.add(root.val); // preorderTraversal(root.left); // preorderTraversal(root.right); // } // return ans; // } // 解法2，迭代,像中序遍历的迭代一样 // public List<Integer> preorderTraversal(TreeNode root) { // List<Integer> ans=new ArrayList(); // Stack<TreeNode> s=new Stack(); // while(root!=null||!s.isEmpty()){ // while(root!=null){ // ans.add(root.val); // s.push(root.right); // root=root.left; // } // root=s.pop(); // } // return ans; // } // 官方迭代解法，先序只需要从右往左压入栈就行了 public List<Integer> preorderTraversal(TreeNode root) { List<Integer> ans=new ArrayList(); Stack<TreeNode> s=new Stack(); if(root==null){ return ans; } s.push(root); while(!s.isEmpty()){ root=s.pop(); ans.add(root.val); if(root.right!=null){ s.push(root.right); } if(root.left!=null){ s.push(root.left); } } return ans; } }