【LeetCode 94】使用迭代返回二叉树的中序遍历结果
程序员文章站
2022-06-17 20:21:36
...
常用递归问题的非递归算法,常常使用栈书写。
第一种:使用栈的非递归中序遍历算法
思路:中序遍历的直观理解。
入栈操作:跟结点出发,将left结点不断添加到栈,到达最后一个结点之后,开始执行出栈操作;
出栈操作:检查栈顶结点是否存在右子树,如果不存在,直接将当前结点弹出并且记录结果;如果存在右子树,在弹出当前结点之后,需要将右子树入栈。
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> answer=new ArrayList<>();
if(root==null) return answer;
LinkedList<TreeNode> stack=new LinkedList<>();
stack.push(root);
while(!stack.isEmpty()){
//不断将左结点加入到栈
while (stack.peek().left != null) {
stack.push(stack.peek().left);
}
//如果栈顶元素不存在右子树,直接记录结果
while(!stack.isEmpty()&&stack.peek().right==null){
TreeNode node=stack.pop();
answer.add(node.val);
}
//如果栈顶元素存在右子树,在弹出栈顶元素之后,需要进入右子树的子结构进行这一系列操作
//因此将右子树的根结点入栈,下一轮循环就会进入右子树的子结构
if(!stack.isEmpty()){
TreeNode node=stack.pop();
answer.add(node.val);
stack.push(node.right);
}
}
return answer;
}
第二种:莫里斯遍历。在访问root结点时,root的左子树已经访问完毕。因此可以直接将root及其右子树直接连接到root左子树的最后一个访问结点的右子树位置上。缺点是会修改树的结构,优点是不需要使用栈等辅助空间。
下一篇: 如何在C代码中使用内联汇编之汇编指令模板