一篇文章教你如何用多种迭代写法实现二叉树遍历
目录
- 思想
- 实现
- 总结
思想
利用栈和队列都可以实现树的迭代遍历。递归的写法将这个遍历的过程交给系统的堆栈去实现了,所以思想都是一样的、无非就是插入值的时机不一样。利用栈的先进先出的特点,对于前序遍历、我们可以先将当前的值放进结果集中,表示的是根节点的值、然后将当前的节点加入到栈中、当前的节点等于自己的left、再次循环的时候、也会将left作为新的节点、直到节点为空、也就是走到了树的最左边、然后回退、也就是弹栈、、也可以认为回退的过程是从低向上的、具体就是让当前的节点等于栈弹出的right、继续重复上面的过程,也就实现了树的前序遍历、也就是bfs.后续遍历、中序遍历思想也是类似的。
实现
public List<Integer> preorderTraversal1(TreeNode root) { List<Integer> res = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); while (!stack.isEmpty() || root != null) { while (root != null) { res.add(root.val); stack.add(root); root = root.left; } TreeNode cur = stack.pop(); root = cur.right; } return res; } public List<Integer> preorderTraversal2(TreeNode root) { List<Integer> res = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); while (!stack.isEmpty() || root != null) { if (root != null) { res.add(root.val); stack.add(root); root = root.left; } else { TreeNode cur = stack.pop(); root = cur.right; } } return res; } public List<Integer> preorderTraversal3(TreeNode root) { List<Integer> res = new ArrayList<>(); if (root == null) return res; Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode cur = stack.pop(); res.add(cur.val); if (cur.right != null) { stack.push(cur.right); } if (cur.left != null) { stack.push(cur.left); } } return res; } public List<Integer> preorderTraversal4(TreeNode root) { List<Integer> res = new ArrayList<>(); if (root == null) { return res; } LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { root = queue.poll(); res.add(root.val); if (root.right != null) { queue.addFirst(root.right); } if (root.left != null) { root = root.left; while (root != null) { res.add(root.val); if (root.right != null) { queue.addFirst(root.right); } root = root.left; } } } return res; } public List<Integer> inorderTraversal1(TreeNode root) { List<Integer> res = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); while (root != null || !stack.isEmpty()) { if (root != null) { stack.add(root); root = root.left; } else { TreeNode cur = stack.pop(); res.add(cur.val); root = cur.right; } } return res; } public List<Integer> inorderTraversal2(TreeNode root) { List<Integer> res = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); while (root != null || !stack.isEmpty()) { while (root != null) { stack.add(root); root = root.left; } TreeNode cur = stack.pop(); res.add(cur.val); root = cur.right; } return res; } public List<Integer> postorderTraversal1(TreeNode root) { List<Integer> res = new ArrayList<>(); if (root == null) return res; Stack<TreeNode> stack = new Stack<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode cur = stack.pop(); res.add(cur.val); if (cur.left != null) { stack.push(cur.left); } if (cur.right != null) { stack.push(cur.right); } } Collections.reverse(res); return res; } public List<Integer> postorderTraversal2(TreeNode root) { List<Integer> res = new ArrayList<>(); Stack<TreeNode> stack = new Stack<>(); while (!stack.isEmpty()) { while (root != null) { res.add(root.val); stack.push(root); root = root.right; } TreeNode cur = stack.pop(); root = cur.left; } Collections.reverse(res); return res; } public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> ret = new ArrayList<>(); if(root == null)return ret; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()){ int size = queue.size(); List<Integer> list = new ArrayList<>(); while(size!=0){ TreeNode cur = queue.poll(); list.add(cur.val); if(cur.left!=null){ queue.offer(cur.left); } if(cur.right!= null){ queue.offer(cur.right); } size --; } ret.add(list); } return ret; }
总结
本篇文章就到这里了,希望能给你带来帮助,也希望您能够多多关注我们的更多内容!
赞 (0)