摘要:題目要求檢查一棵樹是否是左右對稱的。遞歸在這里遞歸的一般情況是,輸入進(jìn)行比較的左子樹和右子樹的根節(jié)點(diǎn),先判斷該倆根節(jié)點(diǎn)是否等價(jià),然后判斷子節(jié)點(diǎn)是否等價(jià)。棧通過棧的形式同樣可以實(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à),然后判斷子節(jié)點(diǎn)是否等價(jià)。
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)依次壓入棧中。每次從棧中取出兩個(gè)進(jìn)行比較的節(jié)點(diǎn)比較。有點(diǎn)像level traversal的思路。
public boolean isSymmetric2(TreeNode treeNode){ if(treeNode==null) return true; LinkedListstack = 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)注我的微信公眾號!將會(huì)不定期的發(fā)放福利哦~
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/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...
摘要:自己沒事刷的一些的題目,若有更好的解法,希望能夠一起探討項(xiàng)目地址 自己沒事刷的一些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ù)雜度時(shí)間空間遞歸棧空間思路如果兩個(gè)根節(jié)點(diǎn)一個(gè)為空,一個(gè)不為空,或者兩個(gè)根節(jié)點(diǎn)值不同,說明出現(xiàn)了不一樣的地方,返回假。代碼遞歸法復(fù)雜度時(shí)間空間遞歸棧空間思路其實(shí)和寫法是一樣的,是比較兩個(gè)節(jié)點(diǎn)的兩個(gè)左邊,然后再比較兩個(gè)節(jié)點(diǎn)的兩個(gè)右邊。 Same Tree Given two binary trees, write a function to check if they are eq...
摘要:微信公眾號記錄截圖記錄截圖目前關(guān)于這塊算法與數(shù)據(jù)結(jié)構(gòu)的安排前。已攻略返回目錄目前已攻略篇文章。會(huì)根據(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 一 目錄 不...
閱讀 1751·2021-09-28 09:43
閱讀 1111·2021-09-23 11:22
閱讀 2707·2021-09-14 18:05
閱讀 1823·2019-08-30 15:52
閱讀 2812·2019-08-30 10:55
閱讀 2007·2019-08-29 16:58
閱讀 1323·2019-08-29 16:37
閱讀 3031·2019-08-29 16:25