Problem
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
ExampleFor example, this binary tree [1,2,2,3,4,4,3] is symmetric:
</>復制代碼
1
/
2 2
/ /
3 4 4 3
But the following [1,2,2,null,3,null,3] is not:
</>復制代碼
1
/
2 2
3 3
Note
Bonus points if you could solve it both recursively and iteratively.
Solution Recursion</>復制代碼
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
return dfs(root.left, root.right);
}
private boolean dfs(TreeNode left, TreeNode right) {
if (left == null) return right == null;
if (right == null) return left == null;
if (left.val != right.val) {
return false;
}
return dfs(left.left, right.right) && dfs(left.right, right.left);
}
}
Iteration
</>復制代碼
class Solution {
public boolean isSymmetric(TreeNode root) {
if (root == null) return true;
Queue queue = new LinkedList<>();
queue.offer(root.left);
queue.offer(root.right);
while (!queue.isEmpty()) {
TreeNode left = queue.poll();
TreeNode right = queue.poll();
if (left == null ^ right == null) return false;
if (left == null && right == null) continue;
if (left.val != right.val) return false;
queue.offer(left.left);
queue.offer(right.right);
queue.offer(left.right);
queue.offer(right.left);
}
return true;
}
}
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://m.specialneedsforspecialkids.com/yun/69270.html
摘要:解題思路所謂的對稱,是左右相反位置的節點的值判斷是否相同。只要出現不同,即可返回即可,否則繼續進行處理。 topic: 101. Symmetric Tree Description: Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For...
摘要:題目要求檢查一棵樹是否是左右對稱的。遞歸在這里遞歸的一般情況是,輸入進行比較的左子樹和右子樹的根節點,先判斷該倆根節點是否等價,然后判斷子節點是否等價。棧通過棧的形式同樣可以實現比較。將需要進行比較的節點依次壓入棧中。 題目要求 Given a binary tree, check whether it is a mirror of itself (ie, symmetric arou...
摘要:遞歸法復雜度時間空間遞歸棧空間思路如果兩個根節點一個為空,一個不為空,或者兩個根節點值不同,說明出現了不一樣的地方,返回假。代碼遞歸法復雜度時間空間遞歸棧空間思路其實和寫法是一樣的,是比較兩個節點的兩個左邊,然后再比較兩個節點的兩個右邊。 Same Tree Given two binary trees, write a function to check if they are eq...
摘要:自己沒事刷的一些的題目,若有更好的解法,希望能夠一起探討項目地址 自己沒事刷的一些LeetCode的題目,若有更好的解法,希望能夠一起探討 Number Problem Solution Difficulty 204 Count Primes JavaScript Easy 202 Happy Number JavaScript Easy 190 Reverse Bi...
摘要:微信公眾號記錄截圖記錄截圖目前關于這塊算法與數據結構的安排前。已攻略返回目錄目前已攻略篇文章。會根據題解以及留言內容,進行補充,并添加上提供題解的小伙伴的昵稱和地址。本許可協議授權之外的使用權限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一 目錄 不...
閱讀 3688·2021-09-22 15:34
閱讀 1200·2019-08-29 17:25
閱讀 3410·2019-08-29 11:18
閱讀 1384·2019-08-26 17:15
閱讀 1755·2019-08-23 17:19
閱讀 1241·2019-08-23 16:15
閱讀 729·2019-08-23 16:02
閱讀 1348·2019-08-23 15:19