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

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

摘要：今天刷后序遍歷非遞歸實(shí)現(xiàn)時(shí)，因?yàn)橐郧翱催^借助一個(gè)棧和隊(duì)列來實(shí)現(xiàn)，但始終模糊不清，不知道如何寫，只好自己捋了一遍，然后查了下，發(fā)現(xiàn)和很多人寫法有差異，故放出來，歡迎指正，如有知道用棧和隊(duì)列方式實(shí)現(xiàn)的朋友，也請(qǐng)賜教。

今天刷后序遍歷非遞歸實(shí)現(xiàn)時(shí)，因?yàn)橐郧翱催^借助一個(gè)棧和隊(duì)列來實(shí)現(xiàn)，但始終模糊不清，不知道如何寫，只好自己捋了一遍，然后查了下，發(fā)現(xiàn)和很多人寫法有差異，故放出來，歡迎指正，如有知道用棧和隊(duì)列方式實(shí)現(xiàn)的朋友，也請(qǐng)賜教。

    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云服務(wù)器云服務(wù)器非遞歸遍歷非遞歸二叉樹遍歷遞歸遍歷java 后序遍歷

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/71564.html

相關(guān)文章

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

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

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

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

FuisonDesign 2019-08-16 16:04 評(píng)論0 收藏0
樹和樹的算法

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

RaoMeng 2019-08-19 11:08 評(píng)論0 收藏0
樹和樹的算法

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

PiscesYE 2019-07-30 17:45 評(píng)論0 收藏0
二叉樹遍歷

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

aboutU 2019-08-26 13:54 評(píng)論0 收藏0