題目介紹

描述：

請實現(xiàn)一個函數(shù)按照之字形順序打印二叉樹，即第一行按照從左到右的順序打印，第二層按照從右到左的順序打印，第三行再按照從左到右的順序打印，其他行以此類推。

例如:
給定二叉樹: [3,9,20,null,null,15,7],

    3
   / \\
  9  20
    /  \\
   15   7
返回其層次遍歷結(jié)果：

[
  [3],
  [20,9],
  [15,7]
]

提示：

節(jié)點總數(shù) <= 1000

解題思路：

遞歸算法的關(guān)鍵是要明確函數(shù)的「定義」是什么，然后相信這個定義，利用這個定義推導(dǎo)最終結(jié)果。

寫樹相關(guān)的算法，簡單說就是，先搞清楚當(dāng)前 root 節(jié)點該做什么，然后根據(jù)函數(shù)定義遞歸調(diào)用子節(jié)點，遞歸調(diào)用會讓孩子節(jié)點做相同的事情。

二叉樹題目的一個難點在于如何通過題目的要求思考出每一個節(jié)點需要做什么

二叉樹解題策略

一 遞歸 二 隊列 + 迭代 （層次遍歷） 三 棧 + 迭代 （非遞歸遍歷） 四 其它

三種基本的遍歷方式，都可以用遞歸來實現(xiàn)。寫遞歸算法的時候，需要注意遞歸退出條件以及遞歸操作的表達(dá)。

自己的解法實現(xiàn)

def levelOrder4(self, root):
        if not root: return []
        res, stack = [], [root]
        while stack:
            tmp = []
            for _ in range(len(stack)):
                node = stack.pop(0)
                tmp.append(node.val)
                if node.left: stack.append(node.left)
                if node.right: stack.append(node.right)
            res.append(tmp[::-1] if len(res) % 2 else tmp)
        return res

網(wǎng)上比較優(yōu)秀的解法

解法一

方法一：層序遍歷 + 雙端隊列 利用雙端隊列的兩端皆可添加元素的特性，設(shè)打印列表（雙端隊列） tmp ，并規(guī)定： 奇數(shù)層 則添加至 tmp 尾部 ， 偶數(shù)層 則添加至 tmp 頭部 。

算法流程：

1. 特例處理： 當(dāng)樹的根節(jié)點為空，則直接返回空列表 [] ；
2. 初始化： 打印結(jié)果空列表 res ，包含根節(jié)點的雙端隊列 deque ；
3. BFS 循環(huán)： 當(dāng) deque 為空時跳出； 4新建列表 tmp ，用于臨時存儲當(dāng)前層打印結(jié)果； 當(dāng)前層打印循環(huán)： 循環(huán)次數(shù)為當(dāng)前層節(jié)點數(shù)（即 deque 長度）； 出隊： 隊首元素出隊，記為 node； 打?。?若為奇數(shù)層，將 node.val 添加至 tmp 尾部；否則，添加至 tmp 頭部； 添加子節(jié)點： 若 node 的左（右）子節(jié)點不為空，則加入 deque ； 將當(dāng)前層結(jié)果 tmp 轉(zhuǎn)化為 list 并添加入 res ； 返回值： 返回打印結(jié)果列表 res 即可；

def levelOrder(self, root):
        from collections import deque
        if not root: return []
        res, queue = [], deque([root])
        while queue:
            tmp = deque()
            for _ in range(len(queue)):
                node = queue.popleft()
                if len(res) % 2:
                    tmp.appendleft(node.val)  # 偶數(shù)層 -> 隊列頭部
                else:
                    tmp.append(node.val)  # 奇數(shù)層 -> 隊列尾部
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            res.append(list(tmp))
        return res

解法二

方法二：層序遍歷 + 雙端隊列（奇偶層邏輯分離） 方法一代碼簡短、容易實現(xiàn)；但需要判斷每個節(jié)點的所在層奇偶性，即冗余了 NN 次判斷。 通過將奇偶層邏輯拆分，可以消除冗余的判斷。 算法流程： 與方法一對比，僅 BFS 循環(huán)不同。

BFS 循環(huán)： 循環(huán)打印奇 / 偶數(shù)層，當(dāng) deque 為空時跳出； 打印奇數(shù)層： 從左向右 打印，先左后右 加入下層節(jié)點； 若 deque 為空，說明向下無偶數(shù)層，則跳出； 打印偶數(shù)層： 從右向左 打印，先右后左 加入下層節(jié)點；

def levelOrder2(self, root):
        from collections import deque
        if not root: return []
        res, queue = [], deque()
        queue.append(root)
        while queue:
            tmp = []
            # 打印奇數(shù)層
            for _ in range(len(queue)):
                # 從左向右打印
                node = queue.popleft()
                tmp.append(node.val)
                # 先左后右加入下層節(jié)點
                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)
            res.append(tmp)
            if not queue: break    # 若為空則提前跳出
            # 打印偶數(shù)層
            tmp = []
            for _ in range(len(queue)):
                # 從右向左打印
                node = queue.pop()
                tmp.append(node.val)
                # 先右后左加入下層節(jié)點
                if node.right:queue.appendleft(node.right)
                if node.left: queue.appendleft(node.left)
            res.append(tmp)
        return res

解法三

方法三：層序遍歷 + 倒序 此方法的優(yōu)點是只用列表即可，無需其他數(shù)據(jù)結(jié)構(gòu)。 偶數(shù)層倒序： 若 res 的長度為 奇數(shù) ，說明當(dāng)前是偶數(shù)層，則對 tmp 執(zhí)行 倒序 操作。

def levelOrder3(self, root):
        from collections import deque
        res, queue = [], deque([root])

        while queue:
            tmp = []
            for _ in range(len(queue)):
                node = queue.popleft()
                tmp.append(node.val)
                if node.left: queue.append(node.left)
                if node.right: queue.append(node.right)
            res.append(tmp[::-1] if len(res)%2 else tmp)
        return res

相關(guān)知識總結(jié)和思考

相關(guān)知識：

BFS：廣度/寬度優(yōu)先。其實就是從上到下，先把每一層遍歷完之后再遍歷一下一層。

可以使用Queue的數(shù)據(jù)結(jié)構(gòu)。我們將root節(jié)點初始化進(jìn)隊列，通過消耗尾部，插入頭部的方式來完成BFS。

二叉搜索樹（BST）的特性：

1. 若它的左子樹不為空，則所有左子樹上的值均小于其根節(jié)點的值
2. 若它的右子樹不為空，則所有右子樹上的值均大于其根節(jié)點的值
3. 它的左右子樹也分別為二叉搜索樹

遞歸與迭代的區(qū)別

遞歸：重復(fù)調(diào)用函數(shù)自身實現(xiàn)循環(huán)稱為遞歸； 迭代：利用變量的原值推出新值稱為迭代，或者說迭代是函數(shù)內(nèi)某段代碼實現(xiàn)循環(huán)；