Leetcode原题
思路
上一篇leetcode _94. 二叉树的中序遍历 。这一篇的做法类似。
首先来说一下什么是前序遍历。
前序遍历：就是先遍历跟节点，然后再遍历左子树、右子树
方法一 递归实现
class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<>(); Deque<TreeNode> statck =new LinkedList<>(); accessTree(root,res); return res; } public void accessTree(TreeNode root, List<Integer> res){ if(root == null){ return; } //递归左中右 res.add(root.val); accessTree(root.left,res); accessTree(root.right,res); } }
递归实现通常很简单，但是会让你忽律很多的细节。
方法二 迭代
方法一的递归函数我们也可以用迭代的方式实现，两种方式是等价的，区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来，其他都相同，具体实现可以看下面的代码。
class Solution { public List<Integer> preorderTraversal(TreeNode root) { //前序遍历： 中左右 List<Integer> res =new ArrayList<>(); Deque<TreeNode> statck =new LinkedList<>(); while(root!=null || !statck.isEmpty()){ while(root!= null){ //遇到跟节点便加入 res.add(root.val); //先添加跟节点 statck.push(root); //然后左节点入栈 root= root.left; } //左节点遍历完，出栈 root = statck.pop(); //遍历右节点 root = root.right; } return res; } }
有兴趣的老爷，还可以关注我的公众号【一起收破烂】，回复【006】获取 最新java面试资料以及简历模型120套哦~
