資訊專欄INFORMATION COLUMN
摘要：題目要求檢查一棵樹是否是左右對稱的。遞歸在這里遞歸的一般情況是，輸入進(jìn)行比較的左子樹和右子樹的根節(jié)點(diǎn)，先判斷該倆根節(jié)點(diǎn)是否等價，然后判斷子節(jié)點(diǎn)是否等價。棧通過棧的形式同樣可以實(shí)現(xiàn)比較。將需要進(jìn)行比較的節(jié)點(diǎn)依次壓入棧中。
題目要求
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For 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.
檢查一棵樹是否是左右對稱的。
遞歸在這里遞歸的一般情況是，輸入進(jìn)行比較的左子樹和右子樹的根節(jié)點(diǎn)，先判斷該倆根節(jié)點(diǎn)是否等價，然后判斷子節(jié)點(diǎn)是否等價。
public boolean isSymmetric(TreeNode treeNode){
if(treeNode==null) return true;
return isSymmetric(treeNode.left, treeNode.right);
}
public boolean isSymmetric(TreeNode left, TreeNode right){
if(left==null && right==null) return true;
if(left!=null && right!=null && left.val==right.val){
return isSymmetric(left.left, right.right)&&isSymmetric(left.right, right.left);
}
return false;
}
棧
通過棧的形式同樣可以實(shí)現(xiàn)比較。將需要進(jìn)行比較的節(jié)點(diǎn)依次壓入棧中。每次從棧中取出兩個進(jìn)行比較的節(jié)點(diǎn)比較。有點(diǎn)像level traversal的思路。
public boolean isSymmetric2(TreeNode treeNode){
if(treeNode==null) return true;
LinkedList stack = new LinkedList();
TreeNode left = treeNode.left, right = treeNode.right;
stack.push(left);
stack.push(right);
while(!stack.isEmpty()){
right = stack.pop();
left = stack.pop();
if(right==null && left==null)continue;
else if(left==null || right==null)return false;
else if(left.val==right.val){
stack.push(left.left);
stack.push(right.right);
stack.push(left.right);
stack.push(right.left);
}else{
return false;
}
}
return true;
}
想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/67455.html
摘要：解題思路所謂的對稱，是左右相反位置的節(jié)點(diǎn)的值判斷是否相同。只要出現(xiàn)不同，即可返回即可，否則繼續(xù)進(jìn)行處理。 topic: 101. Symmetric Tree Description: Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For...
摘要：自己沒事刷的一些的題目，若有更好的解法，希望能夠一起探討項目地址 自己沒事刷的一些LeetCode的題目，若有更好的解法，希望能夠一起探討 Number Problem Solution Difficulty 204 Count Primes JavaScript Easy 202 Happy Number JavaScript Easy 190 Reverse Bi...
Problem Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). Example For example, this binary tree [1,2,2,3,4,4,3] is symmetric: 1 / 2 2 / / 3 ...
摘要：遞歸法復(fù)雜度時間空間遞歸?？臻g思路如果兩個根節(jié)點(diǎn)一個為空，一個不為空，或者兩個根節(jié)點(diǎn)值不同，說明出現(xiàn)了不一樣的地方，返回假。代碼遞歸法復(fù)雜度時間空間遞歸?？臻g思路其實(shí)和寫法是一樣的，是比較兩個節(jié)點(diǎn)的兩個左邊，然后再比較兩個節(jié)點(diǎn)的兩個右邊。 Same Tree Given two binary trees, write a function to check if they are eq...
摘要：微信公眾號記錄截圖記錄截圖目前關(guān)于這塊算法與數(shù)據(jù)結(jié)構(gòu)的安排前。已攻略返回目錄目前已攻略篇文章。會根據(jù)題解以及留言內(nèi)容，進(jìn)行補(bǔ)充，并添加上提供題解的小伙伴的昵稱和地址。本許可協(xié)議授權(quán)之外的使用權(quán)限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一 目錄 不...
閱讀 1774·2021-09-28 09:43
閱讀 1122·2021-09-23 11:22
閱讀 2738·2021-09-14 18:05
閱讀 1832·2019-08-30 15:52
閱讀 2822·2019-08-30 10:55
閱讀 2019·2019-08-29 16:58
閱讀 1332·2019-08-29 16:37
閱讀 3045·2019-08-29 16:25
