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;
    }
}

到此这篇关于java非递归实现之二叉树的前中后序遍历详解的文章就介绍到这了,更多相关Java 二叉树遍历内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！