- 📢前言
- 🌲原題樣例
- 🌻C#方法：遞回
- 🌻Java 方法一：遞回
- 🌻Java 方法二：迭代
- 💬總結
- 🚀往期優質文章分享
📢前言
| 🚀 演算法題 🚀 |
- 🌲 每天打卡一道演算法題，既是一個學習程序，又是一個分享的程序😜
- 🌲 提示：本專欄解題 編程語言一律使用 C# 和 Java 兩種進行解題
- 🌲 要保持一個每天都在學習的狀態，讓我們一起努力成為演算法大神吧🧐！
- 🌲 今天是力扣演算法題持續打卡第27天🎈！
| 🚀 演算法題 🚀 |
🌲原題樣例
給定一個二叉樹，檢查它是否是鏡像對稱的，
例如，二叉樹[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
🌻C#方法：遞回
思路決議
遞回，通常來說一個問題可以分為多個子問題去解決&&問題和求解程序和子問題的求解程序一致&&存在遞回終止條件，滿足這三個條件就適合用遞回，
直接看題目例子的話比較容易發現，鏡像對稱就是二叉樹每層是中心對稱的，
所以可以從頂層遞回看每層是否是這樣的中心對稱，
代碼：
public class Solution {
static bool func(TreeNode x, TreeNode y) {
if (x == null) {
return y == null;
}
if (y == null || x.val != y.val) {
return false;
}
return func(x.left, y.right) && func(x.right, y.left);
}
public bool IsSymmetric(TreeNode root) {
return root == null ? true : func(root.left, root.right);
}
}
執行結果
通過
執行用時：84 ms，在所有 C# 提交中擊敗了88.89%的用戶
記憶體消耗：24.9 MB，在所有 C# 提交中擊敗了91.43%的用戶
復雜度分析
時間復雜度：O(n)
空間復雜度：O(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);
}
}
執行結果
通過
執行用時：0 ms，在所有 Java 提交中擊敗了100.00%的用戶
記憶體消耗：36.5 MB，在所有 Java 提交中擊敗了37.04%的用戶
復雜度分析
時間復雜度：O(min(m+n))其中 mm 和 nn 分別是兩個二叉樹的節點數，對兩個二叉樹同時進行深度優先搜索，只有當兩個二叉樹中的對應節點都不為空時才會訪問到該節點，因此被訪問到的節點數不會超過較小的二叉樹的節點數，
空間復雜度：O(min(m+n))其中 mm 和 nn 分別是兩個二叉樹的節點數，空間復雜度取決于遞回呼叫的層數，遞回呼叫的層數不會超過較小的二叉樹的最大高度，最壞情況下，二叉樹的高度等于節點數，
🌻Java 方法二：迭代
思路決議
「方法一」中我們用遞回的方法實作了對稱性的判斷，那么如何用迭代的方法實作呢？首先我們引入一個佇列，這是把遞回程式改寫成迭代程式的常用方法，
初始化時我們把根節點入隊兩次，
每次提取兩個結點并比較它們的值（佇列中每兩個連續的結點應該是相等的，而且它們的子樹互為鏡像），然后將兩個結點的左右子結點按相反的順序插入佇列中，
當佇列為空時，或者我們檢測到樹不對稱（即從佇列中取出兩個不相等的連續結點）時，該演算法結束，
代碼：
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int p1 = 0, p2 = 0;
int[] sorted = new int[m + n];
int cur;
while (p1 < m || p2 < n) {
if (p1 == m) {
cur = nums2[p2++];
} else if (p2 == n) {
cur = nums1[p1++];
} else if (nums1[p1] < nums2[p2]) {
cur = nums1[p1++];
} else {
cur = nums2[p2++];
}
sorted[p1 + p2 - 1] = cur;
}
for (int i = 0; i != m + n; ++i) {
nums1[i] = sorted[i];
}
}
}
執行結果
通過
執行用時：1 ms，在所有 Java 提交中擊敗了23.81%的用戶
記憶體消耗：37.8 MB，在所有 Java 提交中擊敗了7.81%的用戶
復雜度分析
時間復雜度：O()
空間復雜度：O(n)
💬總結
- 今天是力扣演算法題打卡的第二十七天！
- 文章采用
C#和Java兩種編程語言進行解題 - 一些方法也是參考力扣大神寫的，也是邊學習邊分享，再次感謝演算法大佬們
- 那今天的演算法題分享到此結束啦，明天再見！
🚀往期優質文章分享
- ??Unity零基礎到入門 | 游戲引擎 Unity 從0到1的 系統學習 路線【全面總結-建議收藏】！
- 🧡花一天時間做一個高質量飛機大戰游戲，過萬字Unity完整教程！漂亮學妹看了直呼666！
- 💛回憶童年和小伙伴一起玩過的經典游戲【炸彈人小游戲】制作程序+決議
- 💚通宵一晚做出來的一款類似CS的第一人稱射擊游戲Demo！原來做游戲也不是很難
- 🤍爆肝整整一個周末寫一款類似 皇室戰爭 的 即時戰斗類 游戲Demo！兩萬多字游戲制作程序+決議！
- 💙一款類似“恐龍快打”的 橫版街機格斗游戲 該如何制作？| 一起來學習 順便送原始碼【碼文不易，建議收藏學習】
- 💜【超實用技巧】| 提高寫文的質量 和 速率必學技能： Typora 圖床配置 詳細說明
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/298447.html
標籤：其他