<del id="cgacu"></del>

【刷算法】按照之字形打印二叉樹

phpmatt 發布于2019-08-22 18:46 / 1487人閱讀

摘要：題目描述請實現一個函數按照之字形打印二叉樹，即第一行按照從左到右的順序打印，第二層按照從右至左的順序打印，第三行按照從左到右的順序打印，其他行以此類推分析第一反應可以按照普通的層次遍歷然后再把第等等偶數層的結果翻轉一下，但是那樣子效率太低。

題目描述

請實現一個函數按照之字形打印二叉樹，即第一行按照從左到右的順序打印，第二層按照從右至左的順序打印，第三行按照從左到右的順序打印，其他行以此類推

分析

第一反應可以按照普通的層次遍歷然后再把第2、4、6等等偶數層的結果翻轉一下，但是那樣子效率太低。

上網查閱可以使用雙向隊列，即兩頭都可以進和出。需要從左到右打印的從隊列頭部進入和彈出，需要從右往左打印的從隊列尾部進入和彈出

代碼實現

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */


function Print(r)
{
    if(r === null)
        return [];
    var ds = [];
    var dir = "r";
    var res = [];
    
    ds.unshift(null);
    ds.unshift(r);
    
    while(ds.length > 1) {
        var temp = [];
        if(dir === "r"){
            var cur = ds.shift();
            while(cur !== null) {
                temp.push(cur.val);
                if(cur.left !== null)
                    ds.push(cur.left);
                if(cur.right !== null)
                    ds.push(cur.right)
                cur = ds.shift();
            }
            ds.unshift(null);
        }else{
            var cur = ds.pop();
            while(cur !== null){
                temp.push(cur.val);
                if(cur.right !== null)
                    ds.unshift(cur.right);
                if(cur.left !== null)
                    ds.unshift(cur.left);
                cur = ds.pop();
            }
            ds.push(null);
        }
        
        res.push(temp);
        dir = dir === "r" ? "l" : "r";
    }
    
    return res;
}

module.exports = {
    Print : Print
};

云服務器 GPU云服務器二叉樹算法最優二叉樹算法圖之字形二叉樹

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

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

【刷算法】從上往下打印二叉樹

摘要：題目描述從上往下打印出二叉樹的每個節點，同層節點從左至右打印。分析二叉樹的層次遍歷，可以借助隊列的幫助實現題目描述從上往下打印出二叉樹的每個節點，同層節點從左至右打印。分析二叉樹的層次遍歷，可以借助隊列的幫助實現 /* function TreeNode(x) { this.val = x; this.left = null; this.right =...

ShowerSun 2019-08-22 18:20 評論0 收藏0
【遞歸+迭代詳解】二叉樹的morris遍歷、層序遍歷、前序遍歷、中序遍歷、后序遍歷

摘要：遞歸解法由于層次遍歷的遞歸解法不是主流，因此只介紹前三種的遞歸解法前序遍歷遞歸遞歸中序遍歷遞歸遞歸后序遍歷遞歸遞歸三種遞歸遍歷的總結遞歸終止的條件為碰到空節點。目錄分析二叉樹的前序，中序，后序的遍歷步驟 1.層序遍歷方法一：廣度優先搜索? (以下解釋來自leetcode官方題解) 方法...

niceforbear 2021-11-16 11:45 評論0 收藏0
【刷算法】二叉樹中和為某一值的路徑

摘要：題目描述輸入一顆二叉樹和一個整數，打印出二叉樹中結點值的和為輸入整數的所有路徑。路徑定義為從樹的根結點開始往下一直到葉結點所經過的結點形成一條路徑。思路二叉樹的大多數問題可以使用遞歸來解決，本題亦如此。題目描述輸入一顆二叉樹和一個整數，打印出二叉樹中結點值的和為輸入整數的所有路徑。路徑定義為從樹的根結點開始往下一直到葉結點所經過的結點形成一條路徑。思路二叉樹的大多數問題可以使用...

zxhaaa 2019-08-22 18:21 評論0 收藏0
【刷算法】層次遍歷二叉樹

摘要：題目從上到下按層打印二叉樹，同一層結點從左至右輸出。分析分層次遍歷肯定要使用隊列來完成了，沒啥好分析的代碼實現題目從上到下按層打印二叉樹，同一層結點從左至右輸出。每一層輸出一行。分析分層次遍歷肯定要使用隊列來完成了，沒啥好分析的代碼實現 /* function TreeNode(x) { this.val = x; this.left = null; ...

feng409 2019-08-22 18:46 評論0 收藏0