力扣94题(java语言)
题目
思路
使用一个栈来模拟递归的过程,以非递归的方式完成中序遍历(使用栈可以避免递归调用的空间消耗)。
遍历顺序步骤:
- 遍历左子树
- 访问根节点
- 遍历右子树
package algorithm_leetcode;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class Solution_94 {
public List<Integer> inorderTraversal(TreeNode root) {
// 待处理节点
Stack<TreeNode> stack = new Stack<>();
// 结果
List<Integer> output_arr = new ArrayList<>();
// 如果root为空
if (root == null) {
// 返回空的 output_arr
return output_arr;
}
// 初始化为根节点
TreeNode current = root;
// 循环 只要当前节点不为空,并且栈不为空
while (current != null || !stack.isEmpty()) {
// 当前节点不为空,直到左子树为空
while (current != null) {
// 添加到栈
stack.push(current);
// 当前节点移动到左子节点
current = current.left;
}
// 弹出栈节点
current = stack.pop();
// 添加到结果中
output_arr.add(current.val);
// 如果有右子节点,就移动到右子节点
current = current.right;
}
return output_arr;
}
}
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;
}
}
原文地址:https://blog.csdn.net/bjjgff/article/details/140701337
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!