如何進行Java 數(shù)據(jù)結(jié)構(gòu)中二叉樹前中后序遍歷非遞歸的具體實現(xiàn)

本篇文章為大家展示了如何進行Java 數(shù)據(jù)結(jié)構(gòu)中二叉樹前中后序遍歷非遞歸的具體實現(xiàn)，內(nèi)容簡明扼要并且容易理解，絕對能使你眼前一亮，通過這篇文章的詳細(xì)介紹希望你能有所收獲。

一、前序遍歷

1.題目描述

給你二叉樹的根節(jié)點 root ，返回它節(jié)點值的 前序 遍歷。

2.輸入輸出示例

示例 1：

輸入：root = [1,null,2,3]

輸出：[1,2,3]

示例2：

輸入：root = []

輸出：[]

示例 3：

輸入：root = [1]

輸出：[1]

3.解題思路

前序遍歷：根結(jié)點—左子樹—右子樹

1.判斷額外情況，如果樹為空，直接返回
2.創(chuàng)建一個棧用來保存右子樹
3.先將根結(jié)點入棧，避免多次判斷棧為空
4.取出棧頂元素（第一次為根結(jié)點），從上往下遍歷最左側(cè)路徑中的每個結(jié)點
5.在遍歷時判斷當(dāng)前結(jié)點的右子樹是否為空，非空則入棧
6.遍歷結(jié)束后，此時棧頂元素為前一個結(jié)點的右子樹，將棧頂元素取出，將其看作一棵樹，繼續(xù)重復(fù)上述操作，即形成循環(huán)。

4.代碼實現(xiàn)

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        if(root==null){
            return list;
        }

        //創(chuàng)建一個棧用來保存右子樹
        Stack<TreeNode> s=new Stack<>();
        TreeNode cur=root;
        s.push(root);
        //從上往下遍歷最左側(cè)路徑中的每個結(jié)點，并將其右子樹保存起來---棧
        while(!s.empty()||cur!=null){
            cur=s.pop();
            while(cur!=null){
                list.add(cur.val);
                if(cur.right!=null){
                    s.push(cur.right);
                }
                cur=cur.left; 
            }
        }
        return list;
    }
}

二、中序遍歷

1.題目描述

給定一個二叉樹的根節(jié)點 root ，返回它的 中序 遍歷。

2.輸入輸出示例

示例 1：

輸入：root = [1,null,2,3]

輸出：[1,3,2]

示例 2：

輸入：root = []

輸出：[]

示例 3：

輸入：root = [1]

輸出：[1]

3.解題思路

中序遍歷：左子樹—根結(jié)點—右子樹

1.判斷額外情況，如果樹為空，直接返回
2.創(chuàng)建一個棧用來保存結(jié)點
3.從上往下遍歷最左側(cè)路徑中的每個結(jié)點，并將其保存到棧中，走到cur==null的位置
4.此時棧頂元素為最左側(cè)路徑的最后一個結(jié)點，將其加入到list并將棧頂元素移除
5.判斷最后一個結(jié)點的右子樹是否為空，過程和上述的過程是一樣的，直接將其右子樹看作一棵樹，整個過程便循環(huán)起來

4.代碼實現(xiàn)

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        if(root==null){
            return list;
        }
        Stack<TreeNode> s=new Stack<>();
        TreeNode cur=root;
         //從上往下遍歷最左側(cè)路徑中的每個結(jié)點，并將其保存到棧中
        while(!s.empty()||cur!=null){
            while(cur!=null){
                s.push(cur);
                cur=cur.left;
            }
            cur=s.pop();
            list.add(cur.val);
            cur=cur.right;
        }
        return list;
    }
}

三、后序遍歷

1.題目描述

給定一個二叉樹，返回它的 后序 遍歷。

2.輸入輸出示例

示例:
輸入: [1,null,2,3]
1
\
2
/
3

輸出: [3,2,1]

3.解題思路

后序遍歷：左子樹—右子樹—根結(jié)點

1.判斷額外情況，如果樹為空，直接返回
2.創(chuàng)建一個棧用來保存遍歷的結(jié)點
3找出以cur為根的二叉樹中最左側(cè)的節(jié)點，并保存所經(jīng)路徑中的所有結(jié)點—棧
4.此時棧頂元素為最左側(cè)路徑的最后一個結(jié)點
5.先要判斷最后一個結(jié)點的右子樹是否為空

如果為空，直接將結(jié)點加入list，同時將棧頂元素刪除
如果不為空則將右子樹看作一棵樹，重新進入循環(huán)判斷

注意：如果按照這樣，到了最后的右子樹就會一直循環(huán)出不來
解決方案：
創(chuàng)建一個prev用來標(biāo)記已經(jīng)遍歷過的結(jié)點，將能否編歷的條件改為：top的右子樹為空||top的右子樹已經(jīng)遍歷過

4.代碼實現(xiàn)

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        if(root==null){
            return list;
        }
        Stack<TreeNode> s=new Stack<>();
        TreeNode cur=root;
        TreeNode prev=null;//用來標(biāo)記剛剛遍歷過的節(jié)點
        while(!s.empty()||cur!=null){
            //1.找出以cur為根的二叉樹中最左側(cè)的節(jié)點，并保存所經(jīng)路徑中的所有節(jié)點---棧
            while(cur!=null){
                s.push(cur);
                cur=cur.left;
            }
            TreeNode top=s.peek();
            //top能否遍歷：top的右子樹為空||top的右子樹已經(jīng)遍歷過
            if(top.right==null||top.right==prev){
                list.add(top.val);
                prev=top;
                s.pop();
            }else{
                cur=top.right;
            }  
        }
        return list;
    }
}

上述內(nèi)容就是如何進行Java 數(shù)據(jù)結(jié)構(gòu)中二叉樹前中后序遍歷非遞歸的具體實現(xiàn)，你們學(xué)到知識或技能了嗎？如果還想學(xué)到更多技能或者豐富自己的知識儲備，歡迎關(guān)注億速云行業(yè)資訊頻道。