二叉树中序遍历的非递归实现(栈)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
/* 伪代码:
1. 栈初始化
2. 循环直到root为空且栈为空
2.1 当root非空时循环
2.1.1 将root入栈
2.1.2 继续遍历root的左子树
2.2 如果栈非空,则
2.2.1 栈顶元素弹出至root
2.2.2 输出root.val
2.2.3 准备遍历root的右子树
*/
class BiTreeInOrder {
public List<Integer> inorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
Deque<TreeNode> stack = new ArrayDeque<>();
while(root!=null || stack.size()!=0) {
while(root!=null) {
stack.addFirst(root);
root = root.left;
}
if(stack.size()!=0) {
root = stack.removeFirst();
result.add(root.val);
root = root.right;
}
}
return result;
}
}