欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

一篇文章教你如何用多種迭代寫(xiě)法實(shí)現(xiàn)二叉樹(shù)遍歷

 更新時(shí)間:2021年08月02日 15:40:39   作者:保護(hù)眼睛  
這篇文章主要介紹了C語(yǔ)言實(shí)現(xiàn)二叉樹(shù)遍歷的迭代算法,包括二叉樹(shù)的中序遍歷、先序遍歷及后序遍歷等,是非常經(jīng)典的算法,需要的朋友可以參考下

思想

利用棧和隊(duì)列都可以實(shí)現(xiàn)樹(shù)的迭代遍歷。遞歸的寫(xiě)法將這個(gè)遍歷的過(guò)程交給系統(tǒng)的堆棧去實(shí)現(xiàn)了,所以思想都是一樣的、無(wú)非就是插入值的時(shí)機(jī)不一樣。利用棧的先進(jìn)先出的特點(diǎn),對(duì)于前序遍歷、我們可以先將當(dāng)前的值放進(jìn)結(jié)果集中,表示的是根節(jié)點(diǎn)的值、然后將當(dāng)前的節(jié)點(diǎn)加入到棧中、當(dāng)前的節(jié)點(diǎn)等于自己的left、再次循環(huán)的時(shí)候、也會(huì)將left作為新的節(jié)點(diǎn)、直到節(jié)點(diǎn)為空、也就是走到了樹(shù)的最左邊、然后回退、也就是彈棧、、也可以認(rèn)為回退的過(guò)程是從低向上的、具體就是讓當(dāng)前的節(jié)點(diǎn)等于棧彈出的right、繼續(xù)重復(fù)上面的過(guò)程,也就實(shí)現(xiàn)了樹(shù)的前序遍歷、也就是bfs.后續(xù)遍歷、中序遍歷思想也是類(lèi)似的。

實(shí)現(xiàn)

    public List<Integer> preorderTraversal1(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                res.add(root.val);
                stack.add(root);
                root = root.left;
            }
            TreeNode cur = stack.pop();
            root = cur.right;
        }
        return res;
    }
    public List<Integer> preorderTraversal2(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || root != null) {
            if (root != null) {
                res.add(root.val);
                stack.add(root);
                root = root.left;
            } else {
                TreeNode cur = stack.pop();
                root = cur.right;
            }
        }
        return res;
    }
    public List<Integer> preorderTraversal3(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            res.add(cur.val);
            if (cur.right != null) {
                stack.push(cur.right);
            }
            if (cur.left != null) {
                stack.push(cur.left);
            }
        }
        return res;
    }
    public List<Integer> preorderTraversal4(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            root = queue.poll();
            res.add(root.val);
            if (root.right != null) {
                queue.addFirst(root.right);
            }
            if (root.left != null) {
                root = root.left;
                while (root != null) {
                    res.add(root.val);
                    if (root.right != null) {
                        queue.addFirst(root.right);
                    }
                    root = root.left;
                }
            }
        }
        return res;
    }
    public List<Integer> inorderTraversal1(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            if (root != null) {
                stack.add(root);
                root = root.left;
            } else {
                TreeNode cur = stack.pop();
                res.add(cur.val);
                root = cur.right;
            }
        }
        return res;
    }
    public List<Integer> inorderTraversal2(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.add(root);
                root = root.left;
            }
            TreeNode cur = stack.pop();
            res.add(cur.val);
            root = cur.right;
        }
        return res;
    }
    public List<Integer> postorderTraversal1(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            res.add(cur.val);
            if (cur.left != null) {
                stack.push(cur.left);
            }
            if (cur.right != null) {
                stack.push(cur.right);
            }
        }
        Collections.reverse(res);
        return res;
    }
    public List<Integer> postorderTraversal2(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty()) {
            while (root != null) {
                res.add(root.val);
                stack.push(root);
                root = root.right;
            }
            TreeNode cur = stack.pop();
            root = cur.left;
        }
        Collections.reverse(res);
        return res;
    }
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null)return ret;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            while(size!=0){
                TreeNode cur = queue.poll();
                list.add(cur.val);
                if(cur.left!=null){
                    queue.offer(cur.left);
                }
                if(cur.right!= null){
                    queue.offer(cur.right);
                }
                size --;
            }
            ret.add(list);
        }
        return ret;
    }

總結(jié)

本篇文章就到這里了,希望能給你帶來(lái)幫助,也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容!

相關(guān)文章

  • java原生動(dòng)態(tài)生成驗(yàn)證碼

    java原生動(dòng)態(tài)生成驗(yàn)證碼

    這篇文章主要為大家詳細(xì)介紹了java原生動(dòng)態(tài)生成驗(yàn)證碼,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2020-10-10
  • Java多線(xiàn)程實(shí)現(xiàn)聊天客戶(hù)端和服務(wù)器

    Java多線(xiàn)程實(shí)現(xiàn)聊天客戶(hù)端和服務(wù)器

    這篇文章主要為大家詳細(xì)介紹了Java多線(xiàn)程聊天客戶(hù)端和服務(wù)器實(shí)現(xiàn)代碼,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2016-10-10
  • mybatis-plus 擴(kuò)展批量新增的實(shí)現(xiàn)

    mybatis-plus 擴(kuò)展批量新增的實(shí)現(xiàn)

    本文主要介紹了mybatis-plus 擴(kuò)展批量新增的實(shí)現(xiàn),文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
    2023-01-01
  • Java ScheduledExecutorService定時(shí)任務(wù)案例講解

    Java ScheduledExecutorService定時(shí)任務(wù)案例講解

    這篇文章主要介紹了Java ScheduledExecutorService定時(shí)任務(wù)案例講解,本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下
    2021-08-08
  • Java中的事件處理機(jī)制詳解

    Java中的事件處理機(jī)制詳解

    這篇文章主要介紹了Java中的事件處理機(jī)制詳解,Java事件處理是采取"委派事件模型",當(dāng)事件發(fā)生時(shí),產(chǎn)生事件的對(duì)象,會(huì)把此"信息"傳遞給"事件的監(jiān)聽(tīng)者"處理,這里所說(shuō)的"信息"實(shí)際上就是java.awt.event事件類(lèi)庫(kù)里某個(gè)類(lèi)創(chuàng)建對(duì)象,需要的朋友可以參考下
    2023-09-09
  • JavaWeb Spring依賴(lài)注入深入學(xué)習(xí)

    JavaWeb Spring依賴(lài)注入深入學(xué)習(xí)

    這篇文章主要為大家詳細(xì)介紹了JavaWeb Spring依賴(lài)注入,深入學(xué)習(xí)Spring依賴(lài)注入,感興趣的小伙伴們可以參考一下
    2016-09-09
  • Java的Shiro框架認(rèn)證流程詳解

    Java的Shiro框架認(rèn)證流程詳解

    這篇文章主要介紹了Java的Shiro框架認(rèn)證流程詳解,Shiro 是一個(gè)功能強(qiáng)大和易于使用的安全框架,為開(kāi)發(fā)人員提供一個(gè)直觀而全面的解決方案的認(rèn)證,授權(quán),加密,會(huì)話(huà)管理四大功能,需要的朋友可以參考下
    2024-01-01
  • Mybatis中@Param的用法和作用詳解

    Mybatis中@Param的用法和作用詳解

    這篇文章主要介紹了Mybatis中@Param的用法和作用,在文中給大家補(bǔ)充了spring中@param和mybatis中@param使用區(qū)別,需要的朋友可以參考下
    2017-09-09
  • java高并發(fā)InterruptedException異常引發(fā)思考

    java高并發(fā)InterruptedException異常引發(fā)思考

    這篇文章主要為大家介紹了java高并發(fā)InterruptedException異常引發(fā)思考,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2022-08-08
  • 巧用Spring中的@Order進(jìn)行排序

    巧用Spring中的@Order進(jìn)行排序

    這篇文章主要介紹了巧用Spring中的@Order進(jìn)行排序,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2022-08-08

最新評(píng)論