@TOC

---

前言

代碼隨想錄算法訓練營day15

---

一、Leetcode 102.層序遍歷

1.題目

給你二叉樹的根節(jié)點 root ，返回其節(jié)點值的 層序遍歷 。 (即逐層地，從左到右訪問所有節(jié)點)。

示例 1：

輸入：root = [3,9,20,null,null,15,7] 輸出：[[3],[9,20],[15,7]]

示例 2：

輸入：root = [1] 輸出：[[1]]

示例 3：

輸入：root = [] 輸出：[]

來源：力扣(LeetCode) 鏈接：https://leetcode.cn/problems/binary-tree-level-order-traversal

2.解題思路

方法一：廣度優(yōu)先搜索

思路和算法

我們可以用廣度優(yōu)先搜索解決這個問題。

我們可以想到最樸素的方法是用一個二元組 (node, level) 來表示狀態(tài)，它表示某個節(jié)點和它所在的層數(shù)，每個新進隊列的節(jié)點的 level 值都是父親節(jié)點的 level 值加一。最后根據(jù)每個點的 level 對點進行分類，分類的時候我們可以利用哈希表，維護一個以 level 為鍵，對應節(jié)點值組成的數(shù)組為值，廣度優(yōu)先搜索結束以后按鍵 level 從小到大取出所有值，組成答案返回即可。

考慮如何優(yōu)化空間開銷：如何不用哈希映射，并且只用一個變量 node 表示狀態(tài)，實現(xiàn)這個功能呢？

我們可以用一種巧妙的方法修改廣度優(yōu)先搜索：

首先根元素入隊
當隊列不為空的時候求當前隊列的長度 sisi?依次從隊列中取 sisi? 個元素進行拓展，然后進入下一次迭代

它和普通廣度優(yōu)先搜索的區(qū)別在于，普通廣度優(yōu)先搜索每次只取一個元素拓展，而這里每次取 sisi? 個元素。在上述過程中的第 ii 次迭代就得到了二叉樹的第 ii 層的 sisi? 個元素。

為什么這么做是對的呢？我們觀察這個算法，可以歸納出這樣的循環(huán)不變式：第 ii 次迭代前，隊列中的所有元素就是第 ii 層的所有元素，并且按照從左向右的順序排列。證明它的三條性質(zhì)(你也可以把它理解成數(shù)學歸納法)：

初始化：i=1i=1 的時候，隊列里面只有 root，是唯一的層數(shù)為 11 的元素，因為只有一個元素，所以也顯然滿足「從左向右排列」；
保持：如果 i=ki=k 時性質(zhì)成立，即第 kk 輪中出隊 sksk? 的元素是第 kk 層的所有元素，并且順序從左到右。因為對樹進行廣度優(yōu)先搜索的時候由低 kk 層的點拓展出的點一定也只能是 k+1k+1 層的點，并且 k+1k+1 層的點只能由第 kk 層的點拓展到，所以由這 sksk? 個點能拓展到下一層所有的 sk+1sk+1? 個點。又因為隊列的先進先出(FIFO)特性，既然第 kk 層的點的出隊順序是從左向右，那么第 k+1k+1 層也一定是從左向右。至此，我們已經(jīng)可以通過數(shù)學歸納法證明循環(huán)不變式的正確性。
終止：因為該循環(huán)不變式是正確的，所以按照這個方法迭代之后每次迭代得到的也就是當前層的層次遍歷結果。至此，我們證明了算法是正確的。

3.代碼實現(xiàn)

```java class Solution { public List> levelOrder(TreeNode root) { List> ret = new ArrayList>(); if (root == null) { return ret; }

Queue<TreeNode> queue = new LinkedList<TreeNode>();queue.offer(root);while (!queue.isEmpty()) {List<Integer> level = new ArrayList<Integer>();int currentLevelSize = queue.size();for (int i = 1; i <= currentLevelSize; ++i) {TreeNode node = queue.poll();level.add(node.val);if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}ret.add(level);}return ret;
}

}

```

二、Leetcode 226.翻轉(zhuǎn)二叉樹

1.題目

給你一棵二叉樹的根節(jié)點 root ，翻轉(zhuǎn)這棵二叉樹，并返回其根節(jié)點。

示例 1：

輸入：root = [4,2,7,1,3,6,9] 輸出：[4,7,2,9,6,3,1]

示例 2：

輸入：root = [2,1,3] 輸出：[2,3,1]

示例 3：

輸入：root = [] 輸出：[]

提示：

樹中節(jié)點數(shù)目范圍在 [0, 100] 內(nèi)
-100 <= Node.val <= 100

來源：力扣(LeetCode) 鏈接：https://leetcode.cn/problems/invert-binary-tree

2.解題思路

方法一：遞歸

這是一道很經(jīng)典的二叉樹問題。顯然，我們從根節(jié)點開始，遞歸地對樹進行遍歷，并從葉子節(jié)點先開始翻轉(zhuǎn)。如果當前遍歷到的節(jié)點 rootroot 的左右兩棵子樹都已經(jīng)翻轉(zhuǎn)，那么我們只需要交換兩棵子樹的位置，即可完成以 rootroot 為根節(jié)點的整棵子樹的翻轉(zhuǎn)。

3.代碼實現(xiàn)

```java class Solution { public TreeNode invertTree(TreeNode root) { if (root == null) { return null; } TreeNode left = invertTree(root.left); TreeNode right = invertTree(root.right); root.left = right; root.right = left; return root; } }

```

三、Leetcode 101.對稱二叉樹

1.題目

給你一個二叉樹的根節(jié)點 root ， 檢查它是否軸對稱。

示例 1：

輸入：root = [1,2,2,3,4,4,3] 輸出：true

示例 2：

輸入：root = [1,2,2,null,3,null,3] 輸出：false

提示：

樹中節(jié)點數(shù)目在范圍 [1, 1000] 內(nèi)
-100 <= Node.val <= 100

來源：力扣(LeetCode) 鏈接：https://leetcode.cn/problems/symmetric-tree

2.解題思路

方法一：遞歸

思路和算法

如果一個樹的左子樹與右子樹鏡像對稱，那么這個樹是對稱的。

fig1

因此，該問題可以轉(zhuǎn)化為：兩個樹在什么情況下互為鏡像？

如果同時滿足下面的條件，兩個樹互為鏡像：

它們的兩個根結點具有相同的值
每個樹的右子樹都與另一個樹的左子樹鏡像對稱

fig2

我們可以實現(xiàn)這樣一個遞歸函數(shù)，通過「同步移動」兩個指針的方法來遍歷這棵樹，pp 指針和 qq 指針一開始都指向這棵樹的根，隨后 pp 右移時，qq 左移，pp 左移時，qq 右移。每次檢查當前 pp 和 qq 節(jié)點的值是否相等，如果相等再判斷左右子樹是否對稱。

3.代碼實現(xiàn)

```java class Solution { public boolean isSymmetric(TreeNode root) { return check(root, root); }

public boolean check(TreeNode p, TreeNode q) {if (p == null && q == null) {return true;}if (p == null || q == null) {return false;}return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
}

}

```