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

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

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

思想

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

實現(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é)

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

相關(guān)文章

  • java原生動態(tài)生成驗證碼

    java原生動態(tài)生成驗證碼

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

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

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

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

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

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

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

    Java中的事件處理機制詳解

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

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

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

    Java的Shiro框架認證流程詳解

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

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

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

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

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

    巧用Spring中的@Order進行排序

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

最新評論