树的三种非递归遍历实现

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

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;

    }
}

树的三种非递归遍历实现

原文：https://www.cnblogs.com/wsshub/p/14878913.html