做vi的网站,系统开发是系统建设中工作任务最为繁重的阶段,宁波外贸建站公司,西部数码网站备案核验单题目 思路
使用一个栈来模拟递归的过程#xff0c;以非递归的方式完成中序遍历(使用栈可以避免递归调用的空间消耗)。
遍历顺序步骤#xff1a;
遍历左子树访问根节点遍历右子树
package algorithm_leetcode;import java.util.ArrayList;
import java.util.List;
import…
题目 思路
使用一个栈来模拟递归的过程以非递归的方式完成中序遍历(使用栈可以避免递归调用的空间消耗)。
遍历顺序步骤
遍历左子树访问根节点遍历右子树
package algorithm_leetcode;import java.util.ArrayList;
import java.util.List;
import java.util.Stack;public class Solution_94 {public ListInteger inorderTraversal(TreeNode root) {// 待处理节点StackTreeNode stack new Stack();// 结果ListInteger output_arr new ArrayList();// 如果root为空if (root null) {// 返回空的 output_arrreturn 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;}
}
