Java 后序遍歷非遞歸實現(xiàn)

ymyang 發(fā)布于2019-08-16 12:42 / 1268人閱讀

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

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

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

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

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/71564.html

相關(guān)文章

【從蛋殼到滿天飛】JAVA 數(shù)據(jù)結(jié)構(gòu)解析和算法實現(xiàn)-二分搜索樹

摘要：在數(shù)據(jù)結(jié)構(gòu)領(lǐng)域?qū)?yīng)樹結(jié)構(gòu)來說二叉樹是最常用的一種樹結(jié)構(gòu)，二叉樹具有一個唯一的根節(jié)點，也就是最上面的節(jié)點。二叉樹每個節(jié)點最多有兩個孩子，一個孩子都沒有的節(jié)點通常稱之為葉子節(jié)點，二叉樹每個節(jié)點最多有一個父親，根節(jié)點是沒有父親節(jié)點的。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言...

ghnor 2019-08-23 16:19 評論0 收藏0
【從蛋殼到滿天飛】JAVA 數(shù)據(jù)結(jié)構(gòu)解析和算法實現(xiàn)-二分搜索樹

摘要：在數(shù)據(jù)結(jié)構(gòu)領(lǐng)域?qū)?yīng)樹結(jié)構(gòu)來說二叉樹是最常用的一種樹結(jié)構(gòu)，二叉樹具有一個唯一的根節(jié)點，也就是最上面的節(jié)點。二叉樹每個節(jié)點最多有兩個孩子，一個孩子都沒有的節(jié)點通常稱之為葉子節(jié)點，二叉樹每個節(jié)點最多有一個父親，根節(jié)點是沒有父親節(jié)點的。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言...

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

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

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

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

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

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

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