电子商务网站建设如何实施,网站主题 模板,jsp做电影网站,搭建网站要多少钱#x1f680; 算法题 #x1f680; #x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 #x1f340; #x1f332; 越难的东西,越要努力坚持#xff0c;因为它具有很高的价值#xff0c;算法就是这样✨ #x1f332; 作者简介#xff1a;硕风和炜#xff0c;… 算法题 算法刷题专栏 | 面试必备算法 | 面试高频算法 越难的东西,越要努力坚持因为它具有很高的价值算法就是这样✨ 作者简介硕风和炜CSDN-Java领域优质创作者保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享 恭喜你发现一枚宝藏博主,赶快收入囊中吧 人生如棋我愿为卒行动虽慢可谁曾见我后退一步 算法题 目录 题目链接⛲ 题目描述 求解思路实现代码运行结果⚡ 栈 求解思路 实现代码 运行结果 共勉 题目链接
94. 二叉树的中序遍历
⛲ 题目描述
给定一个二叉树的根节点 root 返回 它的 中序 遍历 。
示例 1
输入root [1,null,2,3] 输出[1,3,2] 示例 2
输入root [] 输出[] 示例 3
输入root [1] 输出[1]
提示
树中节点数目在范围 [0, 100] 内 -100 Node.val 100
进阶: 递归算法很简单你可以通过迭代算法完成吗 求解思路实现代码运行结果 ⚡ 栈 求解思路
创建了一个 ArrayList 用于存储中序遍历的结果通过维护一个栈来记录中序遍历的过程。中序遍历的过程是按照左中右子树遍历。通过cur root表示当前遍历到的节点。具体算法如下:
先收集左子树的所有节点压入栈中收集左子树节点结束弹出此时栈顶的元素收集结果放到List中继续判断此时右子树节点是否为空如果不为空此时遍历指针指向当前节点的右子树节点继续向后遍历。
有了基本的思路接下来我们就来通过代码来实现一下。 实现代码
/*** 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 {public ListInteger inorderTraversal(TreeNode root) {ArrayListInteger ans new ArrayList();if (root null) return ans;DequeTreeNode queue new LinkedList();while (root ! null || !queue.isEmpty()) {while (root ! null) {queue.add(root);root root.left;}TreeNode node queue.pollLast();ans.add(node.val);if (node.right ! null) {root node.right;}}return ans;}
}运行结果 共勉
最后我想和大家分享一句一直激励我的座右铭希望可以与大家共勉
