Java 數據結構中二叉樹前中後序遍歷非遞歸的具體實現詳解

Posted on by

一、前序遍歷

1.題目描述

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

2.輸入輸出示例

示例 1：

在這裡插入圖片描述

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

輸出：[1,2,3]

示例2：

輸入：root = []

輸出：[]

示例 3：

輸入：root = [1]

輸出：[1]

3.解題思路

前序遍歷：根結點—左子樹—右子樹

在這裡插入圖片描述

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

4.代碼實現

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

        //創建一個棧用來保存右子樹
        Stack<TreeNode> s=new Stack<>();
        TreeNode cur=root;
        s.push(root);
        //從上往下遍歷最左側路徑中的每個結點，並將其右子樹保存起來---棧
        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.題目描述

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

2.輸入輸出示例

示例 1：

在這裡插入圖片描述

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

輸出：[1,3,2]

示例 2：

輸入：root = []

輸出：[]

示例 3：

輸入：root = [1]

輸出：[1]

3.解題思路

中序遍歷：左子樹—根結點—右子樹

在這裡插入圖片描述

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

4.代碼實現

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;
         //從上往下遍歷最左側路徑中的每個結點，並將其保存到棧中
        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.解題思路

後序遍歷：左子樹—右子樹—根結點

在這裡插入圖片描述

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

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

註意：如果按照這樣，到瞭最後的右子樹就會一直循環出不來
解決方案：
創建一個prev用來標記已經遍歷過的結點，將能否編歷的條件改為：top的右子樹為空||top的右子樹已經遍歷過

4.代碼實現

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;//用來標記剛剛遍歷過的節點
        while(!s.empty()||cur!=null){
            //1.找出以cur為根的二叉樹中最左側的節點，並保存所經路徑中的所有節點---棧
            while(cur!=null){
                s.push(cur);
                cur=cur.left;
            }
            TreeNode top=s.peek();
            //top能否遍歷：top的右子樹為空||top的右子樹已經遍歷過
            if(top.right==null||top.right==prev){
                list.add(top.val);
                prev=top;
                s.pop();
            }else{
                cur=top.right;
            }  
        }
        return list;
    }
}

以上就是Java 數據結構中二叉樹前中後序遍歷非遞歸的具體實現詳解的詳細內容，更多關於Java 數據結構的資料請關註WalkonNet其它相關文章！

推薦閱讀：