java非递归实现之二叉树的前中后序遍历详解

//非递归

//根 左 右

class Solution {

     public List<Integer> preorderTraversal(TreeNode root) {

         //用数组来存储前序遍历结果

         List<Integer> list = new ArrayList<>();

         if (root== null )  return list;

         //创建一个栈

         Stack<TreeNode> st = new Stack<>();

         //cur指向根节点

         TreeNode cur = root;

         while (!st.isEmpty()||cur!= null ){

             //一边向左遍历，一边将遍历到的节点入栈，节点值入数组

             while (cur!= null ){

                 list.add(cur.val);

                 st.push(cur);   //根

                 cur=cur.left;   //左

             }

             //指针指向栈顶节点（即上一个节点），并将栈顶节点出栈

             cur = st.pop();

             //指针指向该节点的右子树，开始下一轮的遍历

             cur = cur.right;    //右

         }

         return list;

     }

}

//非递归

//左 根 右

class Solution {

     public List<Integer> inorderTraversal(TreeNode root) {

       List<Integer> list = new ArrayList<>();

       if (root== null )    return list;

       Stack<TreeNode> st = new Stack<>();

        TreeNode cur = root;

       while (!st.isEmpty()||cur!= null ){

       //一边向左遍历，一边将遍历到的节点入栈

           while (cur!= null ){

               st.push(cur);

               cur = cur.left;   //左

           }

           cur = st.pop();

           //存储遍历结果

           list.add(cur.val);    //根

           cur = cur.right;      //右

       }

       return list;

     }

}

//非递归

//左 右 根

class Solution {

     public List<Integer> postorderTraversal(TreeNode root) {

      List<Integer> list = new ArrayList<>();

      if (root== null ) return list;

      TreeNode cur = root;

      //关键在于定义一个cur的前驱节点

      TreeNode pre = null ;

      Stack<TreeNode> st = new Stack<>();

      while (cur!= null ||!st.isEmpty()){

         //一边向左遍历，一边将遍历到的节点入栈

          while (cur!= null ){

              st.push(cur);

             cur = cur.left;

          }

          cur = st.pop();

          //若该节点的右节点为空，或者右节点被遍历过，数组才能存储该节点的数值（也就是我们最后才遍历的根）

          if (cur.right== null ||cur.right==pre){

              list.add(cur.val);

              pre = cur;

              cur= null ;

          } else { //如果不满足，说明该节点的右节点还没有被遍历过，那么接着向右子节点遍历

              st.push(cur);

              cur=cur.right;

          }

      }

      return list;

     }

}