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