Java 后序遍歷非遞歸實現

ymyang 發布于2019-08-16 12:42 / 1278人閱讀

摘要：今天刷后序遍歷非遞歸實現時，因為以前看過借助一個棧和隊列來實現，但始終模糊不清，不知道如何寫，只好自己捋了一遍，然后查了下，發現和很多人寫法有差異，故放出來，歡迎指正，如有知道用棧和隊列方式實現的朋友，也請賜教。

今天刷后序遍歷非遞歸實現時，因為以前看過借助一個棧和隊列來實現，但始終模糊不清，不知道如何寫，只好自己捋了一遍，然后查了下，發現和很多人寫法有差異，故放出來，歡迎指正，如有知道用棧和隊列方式實現的朋友，也請賜教。

    public ArrayList postorderTraversal(TreeNode root) {
        ArrayList result = new ArrayList<>();
        if(root==null){
            return result;
        }
        TreeNode node = root;
        Stack stack = new Stack<>();
        Stack markStack = new Stack<>();
        while(node!=null||!stack.isEmpty()){
            while(node!=null){
                stack.push(node);
                node = node.left;
            }
            
            while(!markStack.isEmpty()&&markStack.peek()==stack.peek()){
                  markStack.pop();;
                  result.add(stack.pop().val);
            }
            if(!stack.isEmpty()){
                node = stack.peek();
                markStack.push(node);
                node = node.right;
            }
        }
        
        
        return result;
    }

云服務器 GPU云服務器非遞歸遍歷非遞歸二叉樹遍歷遞歸遍歷java 后序遍歷

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/71564.html

【從蛋殼到滿天飛】JAVA 數據結構解析和算法實現-二分搜索樹

摘要：在數據結構領域對應樹結構來說二叉樹是最常用的一種樹結構，二叉樹具有一個唯一的根節點，也就是最上面的節點。二叉樹每個節點最多有兩個孩子，一個孩子都沒有的節點通常稱之為葉子節點，二叉樹每個節點最多有一個父親，根節點是沒有父親節點的。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言...

ghnor 2019-08-23 16:19 評論0 收藏0
【從蛋殼到滿天飛】JAVA 數據結構解析和算法實現-二分搜索樹

摘要：在數據結構領域對應樹結構來說二叉樹是最常用的一種樹結構，二叉樹具有一個唯一的根節點，也就是最上面的節點。二叉樹每個節點最多有兩個孩子，一個孩子都沒有的節點通常稱之為葉子節點，二叉樹每個節點最多有一個父親，根節點是沒有父親節點的。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言...

FuisonDesign 2019-08-16 16:04 評論0 收藏0
樹和樹的算法

摘要：樹和樹的算法一樹樹的概念樹英語是一種抽象數據類型或是實作這種抽象數據類型的數據結構，用來模擬具有樹狀結構性質的數據集合。一種時間復雜度額外空間復雜度的二叉樹的遍歷方式，為二叉樹的節點個數。樹和樹的算法一、樹 1.1 樹的概念樹（英語：tree）是一種抽象數據類型（ADT）或是實作這種抽象數據類型的數據結構，用來模擬具有樹狀結構性質的數據集合。它是由n（n>=1）個有限節點組成一個...

RaoMeng 2019-08-19 11:08 評論0 收藏0
樹和樹的算法

摘要：樹和樹的算法一樹樹的概念樹英語是一種抽象數據類型或是實作這種抽象數據類型的數據結構，用來模擬具有樹狀結構性質的數據集合。一種時間復雜度額外空間復雜度的二叉樹的遍歷方式，為二叉樹的節點個數。樹和樹的算法一、樹 1.1 樹的概念樹（英語：tree）是一種抽象數據類型（ADT）或是實作這種抽象數據類型的數據結構，用來模擬具有樹狀結構性質的數據集合。它是由n（n>=1）個有限節點組成一個...

PiscesYE 2019-07-30 17:45 評論0 收藏0
二叉樹遍歷

摘要：前言本篇文章是在二叉排序樹的基礎上進行遍歷查找與刪除結點。接下來我們根據構造的這顆二叉樹進行相應遍歷查找與刪除操作。遍歷二叉樹二叉樹的遍歷分為深度優先遍歷和廣度優先遍歷。中序遍歷二叉排序樹，得到的數組是有序的且是升序的。前言本篇文章是在二叉排序樹的基礎上進行遍歷、查找、與刪除結點。那么首先來看一下什么是二叉排序樹？二叉排序樹定義二叉排序樹，又稱二叉查找樹、二叉搜索樹。若...

aboutU 2019-08-26 13:54 評論0 收藏0