2022.2.21 LeetCode —— 二叉树
2022/2/22 0:07:21
本文主要是介绍2022.2.21 LeetCode —— 二叉树,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
文章目录
- 一、今日刷题
- 1. 第六部分:哈希表 -- 144. 二叉树的前序遍历(迭代法)
- 2. 第六部分:哈希表 -- 94. 二叉树的中序遍历(迭代法)
- 3. 第六部分:哈希表 -- 145. 二叉树的后序遍历(迭代法)
- 总结
一、今日刷题
1. 第六部分:哈希表 – 144. 二叉树的前序遍历(迭代法)
跳转LeetCode
给你二叉树的根节点 root ,返回它节点值的 前序 遍历。
答案代码:
前序遍历是中左右,每次先处理的是中间节点,那么先将跟节点放入栈中,然后将右孩子加入栈,再加入左孩子。
为什么要先加入 右孩子,再加入左孩子呢?因为这样出栈的时候才是中左右的顺序。
public List<Integer> inorderTraversal(TreeNode root) { Deque<TreeNode> stack = new ArrayDeque<>(); List<Integer> ans = new ArrayList<>(); stack.push(root); while (!stack.isEmpty()) { TreeNode node = stack.pop(); if (node != null) { ans.add(node.val); } if (node.right != null) { stack.push(node.right); } if (node.left != null) { stack.push(node.left); } } return ans; }
2. 第六部分:哈希表 – 94. 二叉树的中序遍历(迭代法)
跳转LeetCode
给你二叉树的根节点 root ,返回它节点值的 中序 遍历。
答案代码:
public List<Integer> inorderTraversal(TreeNode root) { List<Integer> ans = new ArrayList<>(); Deque<TreeNode> stack = new ArrayDeque<>(); TreeNode cur = root; while (cur != null || !stack.isEmpty()) { if (cur != null) { stack.push(cur); cur = cur.left; } else { cur = stack.pop(); ans.add(cur.val); cur = cur.right; } } return ans; }
3. 第六部分:哈希表 – 145. 二叉树的后序遍历(迭代法)
跳转LeetCode
给你二叉树的根节点 root ,返回它节点值的 后序 遍历。
答案代码:
先序遍历是中左右,后续遍历是左右中,那么我们只需要调整一下先序遍历的代码顺序,就变成中右左的遍历顺序,然后在反转result数组,输出的结果顺序就是左右中了。
(妙!)
public List<Integer> postorderTraversal(TreeNode root) { Deque<TreeNode> stack = new ArrayDeque<>(); List<Integer> ans = new ArrayList<>(); if(root != null) { stack.push(root); } while (!stack.isEmpty()) { TreeNode node = stack.pop(); if (node != null) { ans.add(node.val); } if (node.left != null) { stack.push(node.left); } if (node.right != null) { stack.push(node.right); } } Collections.reverse(ans); return ans; }
总结
在迭代的过程中,其实我们有两个操作:
1.「处理:将元素放进result数组中」
2.「访问:遍历节点」
为什么刚刚写的前序遍历的代码,不能和中序遍历通用呢?
因为前序遍历的顺序是中左右,先访问的元素是中间节点,要处理的元素也是中间节点,所以刚刚才能写出相对简洁的代码,「因为要访问的元素和要处理的元素顺序是一致的,都是中间节点。」
那么再看看中序遍历,中序遍历是左中右,先访问的是二叉树顶部的节点,然后一层一层向下访问,直到到达树左面的最底部,再开始处理节点(也就是在把节点的数值放进result数组中),这就造成了「处理顺序和访问顺序是不一致的。」
那么「在使用迭代法写中序遍历,就需要借用指针的遍历来帮助访问节点,栈则用来处理节点上的元素。」
这篇关于2022.2.21 LeetCode —— 二叉树的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升