https://www.jianshu.com/p/456af5480cee
一、先序遍历
考察到一个节点后,即刻输出该节点的值,并继续遍历其左右子树。(根左右)
public static void 先序非递归(TreeNode root)
{
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;
//节点不为空或者栈不为空都要循环
while(node != null || !stack.empty())
{
// 1. 输出根节点的值
// 2. 保存根节点(方便后面找右节点)
// 3. 找到最左节点
while(node != null)
{
System.out.println(node.val+" ");
stack.push(node);
node = node.left;
}
//找到右节点
if(!stack.empty())
{
node = stack.pop();
node = node.right;
}
}
}
二、中序遍历
永远先考虑左子树,直到左子树为空才访问根节点
//2.中序非递归
public static void 中序非递归(TreeNode root)
{
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;
//节点不为空或者栈不为空都要循环
while(node != null || !stack.empty())
{
// 1. 保存根节点(方便后面找右节点)
// 2. 找到最左节点
while(node != null)
{
stack.push(node);
node = node.left;
}
if(!stack.empty())
{
node = stack.pop();
System.out.println(node.val+" ");
node = node.right;
}
}
}
三、后序遍历
后序遍历在决定是否可以输出当前节点的值的时候,需要考虑其左右子树是否都已经遍历完成。
所以需要设置一个lastVisit游标。
若lastVisit等于当前考查节点的右子树,表示该节点的左右子树都已经遍历完成,则可以输出当前节点。
并把lastVisit节点设置成当前节点,将当前游标节点node设置为空,下一轮就可以访问栈顶元素。
否则,需要接着考虑右子树,node = node.right。
后续遍历的三种情况:
public static void 后序非递归(TreeNode root)
{
Stack<TreeNode> stack = new Stack<>();
TreeNode node =root;
TreeNode lastVisit = root;
while(node != null || !stack.empty())
{
while(node != null){
stack.push(node);
node = node.left;
}
//查看当前栈顶元素
node = stack.peek();
//如果其右子树也为空,或者右子树已经访问
//则可以直接输出当前节点的值
if(node.right == null || node.right==lastVisit){
System.out.println(node.val+" ");
stack.pop();
lastVisit=node;
node=null;
}else{
//否则,继续遍历右子树
node=node.right;
}
}
}