力扣初級演算法（四）【樹】
本文中的題目均來自力扣，代碼默認以C#實作，偽代碼僅用來幫助描述，不嚴格遵循某種語言的語法，
樹比鏈表稍微復雜，因為鏈表是線性資料結構，而樹不是， 樹的問題可以由
廣度優先搜索或深度優先搜索解決， 在本章節中，我們提供了一個對于練習廣度優先遍歷很好的題目，我們推薦以下題目：二叉樹的最大深度，驗證二叉搜索樹，二叉樹的層次遍歷 和 將有序陣列轉換為二叉搜索樹，
- 在開始題目之前，我們先給出樹中節點的定義，
/* Definition for a binary tree node. */
public class TreeNode
{
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
104. 二叉樹的最大深度
難度：簡單
給定一個二叉樹，找出其最大深度，
二叉樹的深度為根節點到最遠葉子節點的最長路徑上的節點數，
說明: 葉子節點是指沒有子節點的節點，
示例： 給定二叉樹
[3,9,20,null,null,15,7]，3 / \ 9 20 / \ 15 7回傳它的最大深度 3 ，
解題思路
-
樸素的想法是，進行深度優先遍歷，找到一個最大的深度并回傳，
-
通常，我們通過遞回的方式來實作深度優先遍歷，
本題需要的結果是深度，那么我們就應該回傳一個深度
-
然后從回傳的深度中找到一個最大值，
-
對于任意一個節點來說，尋找深度的問題可以拆分成兩個子問題，
- 即左子樹的深度和右子樹的深度，我們將問題交給他們來解決，
- 選擇得到的結果中更大的那一個，在加上此節點本身的深度
1， - 最后將得到的結果回傳即可，
-
遞回的程序不可能無止境的進行下去，通常有一個終點，
-
對于本題來說，當一個節點為空節點的時候，肯定沒有左右節點，
所以不用拋出問題，直接回傳 0 即可，
方法一：深度優先
public int MaxDepth(TreeNode root)
{
if (root is null) return 0; // 遞回的終點
return Math.Max(MaxDepth(root.left), MaxDepth(root.right)) + 1;
}
-
那么如何通過廣度優先來得到最大深度呢？
-
對于廣度優先來說，我們通常借助佇列來實作，
這里我們先簡單介紹一下C#語言當中的佇列結構，
// 摘要: 表示物件的先進先出集合， // 型別引數: T: 指定佇列中元素的型別， public class Queue<T> : IEnumerable<T>, ICollection, IEnumerable { /* ... */ public int Count { get; } // 包含的元素數， public void Clear(); // 移除所有物件， public T Dequeue(); // 移除并回傳位于Queue開始處的物件 public void Enqueue(T item); // 將物件添加到Queue的結尾處 public T Peek(); // 回傳位于Queue開始處的物件但不將其移除， /* ... */ } -
通常的廣度優先是，一層一層的遍歷二叉樹，
在遍歷的同時將每個節點的左右節點加入到佇列當中，
-
由于佇列先進先出的性質我們可以在保證在遍歷到下一層之前，當前層全部訪問到，
-
但是廣度優先要想求得深度，也就是當前遍歷到了第幾層，
就需要做一些微妙的調整了，
-
我們可以一次性拿出佇列中全部的節點，
然后將新添加的節點再次加入到佇列當中，
這樣，每次從佇列中拿出全部的節點，
都相當于遍歷到了新的一層，也就是深度加一，
方法二：廣度優先
public int MaxDepth(TreeNode root)
{
var res = 0;
var queue = new Queue<TreeNode>();
if (root!=null) queue.Enqueue(root);
while (queue.Any())
{
res++;
// 一次性拿出這一層的節點
List<TreeNode> list = queue.ToList();
queue.Clear();
foreach (var note in list)
{
if (note.left != null) queue.Enqueue(note.left);
if (note.right != null) queue.Enqueue(note.right);
}
}
return res;
}
98. 驗證二叉搜索樹
難度：中等
給定一個二叉樹，判斷其是否是一個有效的二叉搜索樹，
假設一個二叉搜索樹具有如下特征：
- 節點的左子樹只包含小于當前節點的數，
- 節點的右子樹只包含大于當前節點的數，
- 所有左子樹和右子樹自身必須也是二叉搜索樹，
示例 1:
輸入: 2 / \ 1 3 輸出: true示例 2:
輸入: 5 / \ 1 4 / \ 3 6 輸出: false 解釋: 輸入為: [5,1,4,null,null,3,6]， 根節點的值為 5 ，但是其右子節點值為 4 ，
解題思路
-
樸素的想法是，對于每一個節點，我們都驗證一下它滿不滿足二叉搜索樹的規則，一旦找到一個不滿足的節點，就停止搜索，
-
一種樸素的做法是，對于每一個節點，我們遍歷它的左子樹和右子樹，如果左子樹中的每個節點都小于根節點，則符合要求，右子樹同理，
bool IsValidBST(TreeNode root) { if (FindLeft(root) and FindRight(root)) : return IsValidBST(root.left) and IsValidBST(root.right); else : return False; } -
但是我們很快就發現，這個解法中有大量重復的程序，對于每一個節點，我們都遍歷了它的左右子樹，這其實是沒有必要的，
-
我們完全可以判斷一下每個節點的范圍區間，在一次遍歷中得到結果，
- 我們可以動態的維護一個大小區間，只要當前節點在這個區間內即可，
方法一：深度優先
public bool IsValidBST(TreeNode root)
{
return IsValidBST(root, null, null);
bool IsValidBST(TreeNode node, int? min, int? max)
{
if (node is null) return true;
if ((min is null || node.val > min) && (max is null || node.val < max))
{
return IsValidBST(node.left, min, node.val) && IsValidBST(node.right, node.val, max);
}
return false;
}
}
- 當然，對于二叉搜索樹來說，中序遍歷的結果一定是升序的，我們可以利用這個特性來驗證是否是二叉搜索樹，
方法二：中序遍歷
public bool IsValidBST(TreeNode root)
{
int? last = null;
return IsValidBST(root);
bool IsValidBST(TreeNode note)
{
if (note is null) return true;
// 中序遍歷
if (IsValidBST(note.left)) // 左
{
if (last is null || note.val > last) // 根
{
last = note.val;
return (IsValidBST(note.right)); // 右
}
}
return false;
}
}
101. 對稱二叉樹
難度：簡單
給定一個二叉樹，檢查它是否是鏡像對稱的，
例如，二叉樹
[1,2,2,3,4,4,3]是對稱的，1 / \ 2 2 / \ / \ 3 4 4 3但是下面這個
[1,2,2,null,3,null,3]則不是鏡像對稱的:1 / \ 2 2 \ \ 3 3進階：
你可以運用遞回和迭代兩種方法解決這個問題嗎？
解題思路
- 如果我們直接觀察這顆二叉樹，是不是很容易就能看出它是不是鏡像？
- 我們的大腦是如何思考的呢？
- 我們大概率會用我們的雙眼去掃描這顆二叉樹，看看左右兩邊哪里不同，
- 那么對于計算機來說，我們也可以讓它分別掃描根節點的左右子樹，然后判斷是否相同，
- 這里我們借助兩個額外的容器來存放掃描的記錄，
- 我們分別對左右子樹進行進行
根左右和根右左順序的遍歷，如果左右子樹是鏡像的，那么我們遍歷得到的記錄應該是相同的，
- 我們分別對左右子樹進行進行
方法一：左右遍歷
public bool IsSymmetric(TreeNode root)
{
var leftList = new List<int?>();
var rightList = new List<int?>();
FindLeft(root?.left);
FindRight(root?.right);
return leftList.SequenceEqual(rightList);
// 根左右 遍歷左子樹
void FindLeft(TreeNode node)
{
leftList.Add(node?.val);
if (node is null) return; // 遞回的終點
FindLeft(node.left);
FindLeft(node.right);
}
// 根右左 遍歷右子樹
void FindRight(TreeNode node)
{
rightList.Add(node?.val);
if (node is null) return; // 遞回的終點
FindRight(node.right);
FindRight(node.left);
}
}
-
在上面的做法當中，我們對左右子樹進行了完全遍歷，并使用兩個容器來保存，這其實是沒有必要的，
-
我們人腦在識別的時候，也不過是兩個節點兩個節點的對比，那么計算機能否也這樣呢？
-
我們找到了一個最小的操作，對比兩個節點的值，
如果相等，就拋出問題，繼續對比后面的節點，如果不相等，就立刻終止，
方法二：遞回
public bool IsSymmetric(TreeNode root)
{
return IsSymmetric(root?.left, root?.right);
bool IsSymmetric(TreeNode left, TreeNode right)
{
if (left is null && right is null) return true; // 遞回的終點
return (left?.val == right?.val) && IsSymmetric(left.left, right.right) && IsSymmetric(left.right, right.left);
}
}
- 除此之外，廣度優先也是一種不錯的解法，我們在前面的題目當中已經做過逐層掃描的操作了，這一次我們也可以這么干，
- 對于每一層的節點，如果二叉樹是鏡像的，那么這一層的節點也應該是鏡像的，我們可以利用老朋友雙指標來判斷，
方法三：廣度優先
public bool IsSymmetric(TreeNode root)
{
if (root is null) return true;
var queue = new Queue<TreeNode>();
queue.Enqueue(root);
while (queue.Any())
{
List<TreeNode> list = queue.ToList();
// 雙指標判斷是否鏡像
for (int i = 0, j = list.Count - 1; i < j; i++, j--)
if (list[i]?.val != list[j]?.val) return false;
queue.Clear();
foreach (var node in list)
{
if (node != null)
{
queue.Enqueue(node.left);
queue.Enqueue(node.right);
}
}
}
return true;
}
102. 二叉樹的層序遍歷
難度：中等
給你一個二叉樹，請你回傳其按 層序遍歷 得到的節點值， （即逐層地，從左到右訪問所有節點），
示例： 二叉樹：
[3,9,20,null,null,15,7],3 / \ 9 20 / \ 15 7回傳其層次遍歷結果：
[ [3], [9,20], [15,7] ]
解題思路
- 樸素的想法是，利用廣度優先逐層遍歷，像我們之前做的那樣，每次直接取出一層的節點，
- 不過在此之前，我們先考慮一下深度優先的解法，我們是不是可以通過一個額外的欄位深度來記錄當前遍歷節點的深度，然后再把它加入到對應的深度集合當中呢？
方法一：深度優先
public IList<IList<int>> LevelOrder(TreeNode root)
{
var res = new List<IList<int>>();
FindP(root, 0);
return res;
void FindP(TreeNode node, int depth)
{
if (node is null) return; // 遞回的終點
if (res.Count <= depth) res.Add(new List<int>()); // 擴容
res[depth].Add(node.val);
FindP(node.left, depth + 1);
FindP(node.right, depth + 1);
}
}
-
廣度優先的寫法很簡單，除了直接取出一層節點外，
我們還可以取出佇列的前N個節點，N為當前層的節點數量，這樣可以保證每次取的都是同一層節點，
方法二：廣度優先
public IList<IList<int>> LevelOrder(TreeNode root)
{
var res = new List<IList<int>>();
var queue = new Queue<TreeNode>();
if (root != null) queue.Enqueue(root);
for (var depth = 0; queue.Any(); depth++)
{
var temp = new List<int>();
var n = queue.Count; // 取n個節點填充
for (int i = 0; i < n; i++)
{
var note = queue.Dequeue();
temp.Add(note.val);
if (note.left != null) queue.Enqueue(note.left);
if (note.right != null) queue.Enqueue(note.right);
}
res.Add(temp);
}
return res;
}
108. 將有序陣列轉換為二叉搜索樹
難度：簡單
將一個按照升序排列的有序陣列，轉換為一棵高度平衡二叉搜索樹，
本題中，一個高度平衡二叉樹是指一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過 1，
示例:
給定有序陣列: [-10,-3,0,5,9], 一個可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面這個高度平衡二叉搜索樹： 0 / \ -3 9 / / -10 5
解題思路
- 樸素的想法是，先找到一個最小的操作，對于平衡的二叉搜索樹來說，由于給定的陣列是有序的，那么我們很容易想到，把這個陣列最中間的元素當做根節點的值，
- 這樣，我們就把陣列劃分成了三部分，左邊、中間、右邊，
- 左邊和右邊區間的長度差值不會超過1，而且都是升序的，用來構造平衡的二叉搜索樹再好不過了，
- 我們可以將問題拋出，只利用最中間的元素來構造一個根節點，左右子樹的構造交給一個函式來解決，
方法一：遞回
public TreeNode SortedArrayToBST(int[] nums)
{
if (nums.Length < 1) return null;
var mid = nums.Length / 2;
return new TreeNode(nums[mid])
{
left = SortedArrayToBST(nums.Take(mid).ToArray()),
right = SortedArrayToBST(nums.Skip(mid + 1).ToArray())
};
}
- 對二叉平衡樹感興趣的同學，還可以自行了解一下二叉平衡樹插入節點和洗掉節點的實作，
最后
- 遞回是非常有魅力的一種寫法，你可以只關心區域的作業，然后將剩余的問題拋出，
- 二叉樹的遍歷和鏈表的遍歷是不是非常相似？只不過每個節點可以延伸到兩個節點，而鏈表只會延伸一個節點，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/176534.html
標籤：其他
上一篇：丑數
下一篇：目標檢測中焦點損失的入門指南！