树的三种非递归遍历实现

先序:(每个节点左下延伸,沿途依次访问,且沿途依次将右孩子入栈。不能左下时,让出栈节点执行前面的过程)

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        LinkedList<Integer> ans=new LinkedList<>();
        LinkedList<TreeNode> sta=new LinkedList<>();
        TreeNode p=root;
        while(p!=null||!sta.isEmpty()){
          while(p!=null){
              ans.add(p.val);//访问
              sta.add(p.right);//右孩子入栈
              p=p.left;//往左下延伸
          }
          p=sta.removeLast();//让栈顶也做一次上面的循环
        }
    return ans;
    }
}

中序:(每个节点沿左下延伸,沿途节点不访问并入栈。出栈一个访问一个,出栈的右孩子执行前面的过程)

class Solution {

    public List<Integer> inorderTraversal(TreeNode root) {
        LinkedList<Integer> ans=new LinkedList<>();
        LinkedList<TreeNode> sta=new LinkedList<>();
        TreeNode p=root;
        while(p!=null||!sta.isEmpty()){
          while(p!=null){
              sta.add(p);//左下延伸,沿途的节点不访问,入栈
              p=p.left;
          }
          TreeNode node=sta.removeLast();
          ans.add(node.val);
          p=node.right;

        }
        return ans;
    }
}

后序(链表的插入和先序不一样,且入栈的顺序相反):


class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        LinkedList<Integer> ans=new LinkedList<>();
        LinkedList<TreeNode> sta=new LinkedList<>();
        TreeNode p=root;
        while(p!=null||!sta.isEmpty()){
            while(p!=null){
                ans.addFirst(p.val);
                sta.add(p.left);
                p=p.right;
            }
            p=sta.removeLast();
        }
        return ans;

    }
}
上一篇:LR分析程序


下一篇:luogu P6239 奇怪的道路