合肥网站建设技术,wordpress目录seo,维恩图在线制作网站,兼职做效果图的网站Hi~#xff01;这里是奋斗的明志#xff0c;很荣幸您能阅读我的文章#xff0c;诚请评论指点#xff0c;欢迎欢迎 ~~ #x1f331;#x1f331;个人主页#xff1a;奋斗的明志 #x1f331;#x1f331;所属专栏#xff1a;数据结构、LeetCode专栏 #x1f4da;本系… Hi~这里是奋斗的明志很荣幸您能阅读我的文章诚请评论指点欢迎欢迎 ~~ 个人主页奋斗的明志 所属专栏数据结构、LeetCode专栏 本系列文章为个人学习笔记在这里撰写成文一为巩固知识二为展示我的学习过程及理解。文笔、排版拙劣望见谅。 力扣练习题 一、根据二叉树创建字符串1.题目2.解析3.完整代码深度优先遍历4.复杂度分析 二、二叉树的前序遍历非递归1.题目2.解析3.完整代码 三、二叉树的中序遍历非递归1.题目2.解析3.完整代码 四、二叉树的后序遍历非递归1.题目2.解析3.完整代码 总结 一、根据二叉树创建字符串
606.根据二叉树创建字符串 1.题目 2.解析
利用前序遍历在递归的同时有四种情况如下
【第一、二种】
如果当前节点有两个孩子那我们在递归时需要在两个孩子的结果外都加上一层括号如果当前节点没有孩子那我们不需要在节点后面加上任何括号在本题可以省略 【第三种】
如果当前节点只有左孩子那我们在递归时只需要在左孩子的结果外加上一层括号而不需要给右孩子加上任何括号 【第四种】
如果当前节点只有右孩子那我们在递归时需要先加上一层空的括号 ‘()’ 表示左孩子为空再对右孩子进行递归并在结果外加上一层括号。 3.完整代码深度优先遍历 /*** 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 String tree2str(TreeNode root) {//创建 StringBuilder 存储字符串StringBuilder sbu new StringBuilder();tree2strChild(root,sbu);return sbu.toString();}public void tree2strChild(TreeNode root, StringBuilder sbu) {//先判断根节点if(root null){return;}//代码走到这说明该树不为空//把 结点的值添加sbu.append(root.val);//进行递归//因为题目要求的是前序遍历 根左右//接下来判断左子树//左树可能为空 可能不为空if(root.left ! null){//左子树不为空先添加 一个 左小括号sbu.append(();//开始递归左树tree2strChild(root.left,sbu);//左树递归完了 加一个右小括号sbu.append());}else{if(root.right null){return;}else{sbu.append(());}}//接下来判断右子树//右树可能为空 可能不为空if(root.right ! null){sbu.append(();//开始递归右树tree2strChild(root.right,sbu);sbu.append());}else{return;}}
}4.复杂度分析 时间复杂度O(n)其中 n 是二叉树中的节点数目。 空间复杂度O(n)。在最坏情况下会递归 n 层。 本题也可以用迭代来实现需要借助栈进行辅助 二、二叉树的前序遍历非递归
144.二叉树的前序遍历
1.题目 2.解析
前序遍历根节点 -- 左子树 -- 右子树 借助栈来辅助完成使用 while 循环进行迭代条件是 cur 不为空或者栈 stack 不为空。这保证了在遍历完所有节点后退出循环。内部的第一个 while 循环用于将当前节点 cur 及其左子节点一直压入栈中并将节点值 cur.val 添加到 list 中直到没有左子节点为止。当没有左子节点时从栈中弹出栈顶节点 top并将 cur 设置为 top 的右子节点 top.right。这样在下一轮循环中就会处理右子树的节点。 3.完整代码 /*** 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 preorderTraversal(TreeNode root) {ListInteger list new ArrayList();if (root null) {return list;}// 如果 root 不等于空TreeNode cur root;// 创建一个栈StackTreeNode stack new Stack();while (cur ! null || !stack.isEmpty()) {while (cur ! null) {stack.push(cur);list.add(cur.val);cur cur.left;}// 弹出一个元素 给一个中间变量TreeNode top stack.pop();// 新的cur top的rightcur top.right;}return list;}
}三、二叉树的中序遍历非递归
94.二叉树的中序遍历
1.题目 2.解析
中序遍历左子树 -- 根节点 -- 右子树 3.完整代码 /*** 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) {// 用来存储元素ListInteger list new ArrayList();if (root null) {return list;}TreeNode cur root;// 创建一个栈 存放结点 用来维护StackTreeNode stack new Stack();while (cur ! null || !stack.isEmpty()) {while (cur ! null) {// 先入栈stack.push(cur);cur cur.left;}// 定义一个临时节点TreeNode top stack.pop();list.add(top.val);cur top.right;}return list;}
}四、二叉树的后序遍历非递归
145.二叉树的后序遍历
1.题目 2.解析 前序遍历左子树 -- 右子树 -- 根节点 迭代遍历过程
while (cur ! null || !stack.isEmpty()) {while (cur ! null) {// 将当前节点及其左子节点依次压入栈中stack.push(cur);cur cur.left;}TreeNode top stack.peek();if (top.right null || top.right prev) {// 如果栈顶节点的右子节点为空或者已经访问过stack.pop(); // 弹出栈顶节点list.add(top.val); // 将栈顶节点值加入结果列表prev top; // 更新 prev 指向已访问过的节点} else {// 否则处理右子节点cur top.right;}
}
外层的 while 循环保证在当前节点 cur 不为空或者栈 stack 不为空时继续迭代。内部的第一个 while 循环将当前节点 cur 及其所有左子节点一直压入栈中直到没有左子节点。stack.peek() 获取栈顶节点 top然后检查其右子节点 如果右子节点为空 top.right null 或者右子节点已经被访问过 top.right prev则表示可以访问当前节点 top因此将其从栈中弹出并将节点值 top.val 加入 list 中。更新 prev 指向当前已经访问过的节点 top。否则将 cur 设置为当前节点 top 的右子节点以便下一轮迭代时处理右子树。
3.完整代码 /*** 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 postorderTraversal(TreeNode root) {ListInteger list new ArrayList();if (root null) {return list;}TreeNode cur root;TreeNode prev null;StackTreeNode stack new Stack();while (cur ! null || !stack.isEmpty()) {while (cur ! null) {// 压栈stack.push(cur);cur cur.left;}TreeNode top stack.peek();if (top.right null || top.right prev) {stack.pop();list.add(top.val);prev top;} else {cur top.right;}}return list;}
}这段代码通过栈实现了二叉树的后序遍历利用了一个额外的 prev 变量来跟踪已经访问过的节点从而在处理完右子树后能正确处理根节点。这种方法相较于递归实现更为复杂但在一些情况下可能更高效。 总结
递归函数我们也可以用迭代的方式实现两种方式是等价的区别在于递归的时候隐式地维护了一个栈而我们在迭代的时候需要显式地将这个栈模拟出来其他都相同.
