【leetcode】根据二叉树创建字符串、二叉树的前中后遍历（非递归链表实现二叉树）

Hi~！这里是奋斗的明志，很荣幸您能阅读我的文章，诚请评论指点，欢迎欢迎 ~~
🌱🌱个人主页：奋斗的明志
🌱🌱所属专栏：数据结构、LeetCode专栏

📚本系列文章为个人学习笔记，在这里撰写成文一为巩固知识，二为展示我的学习过程及理解。文笔、排版拙劣，望见谅。

`

---

一、根据二叉树创建字符串

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 List<Integer> preorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();if (root == null) {return list;}// 如果 root 不等于空TreeNode cur = root;// 创建一个栈Stack<TreeNode> 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 List<Integer> inorderTraversal(TreeNode root) {// 用来存储元素List<Integer> list = new ArrayList<>();if (root == null) {return list;}TreeNode cur = root;// 创建一个栈 存放结点 用来维护Stack<TreeNode> 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 List<Integer> postorderTraversal(TreeNode root) {List<Integer> list = new ArrayList<>();if (root == null) {return list;}TreeNode cur = root;TreeNode prev = null;Stack<TreeNode> 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 变量来跟踪已经访问过的节点，从而在处理完右子树后能正确处理根节点。这种方法相较于递归实现更为复杂，但在一些情况下可能更高效。

总结

递归函数我们也可以用迭代的方式实现，两种方式是等价的，区别在于递归的时候隐式地维护了一个栈，而我们在迭代的时候需要显式地将这个栈模拟出来，其他都相同.