這篇文章將為大家詳細講解有關LeetCode中如何解決相同的樹問題,小編覺得挺實用的,因此分享給大家做個參考,希望大家閱讀完這篇文章后可以有所收獲。
成都做網(wǎng)站、網(wǎng)站設計服務團隊是一支充滿著熱情的團隊,執(zhí)著、敏銳、追求更好,是創(chuàng)新互聯(lián)的標準與要求,同時竭誠為客戶提供服務是我們的理念。成都創(chuàng)新互聯(lián)把每個網(wǎng)站當做一個產(chǎn)品來開發(fā),精雕細琢,追求一名工匠心中的細致,我們更用心!
https://leetcode-cn.com/problems/same-tree/
給定兩個二叉樹,編寫一個函數(shù)來檢驗它們是否相同。
如果兩個樹在結(jié)構(gòu)上相同,并且節(jié)點具有相同的值,則認為它們是相同的。
示例 1:
輸入: 1 1
/ \ / \
2 3 2 3
[1,2,3], [1,2,3]
輸出: true
示例 2:
輸入: 1 1
/ \
2 2
[1,2], [1,null,2]
輸出: false
示例 3:
輸入: 1 1
/ \ / \
2 1 1 2
[1,2,1], [1,1,2]
輸出: false
標簽:深度優(yōu)先遍歷
終止條件與返回值:
當兩棵樹的當前節(jié)點都為null時返回true
當其中一個為null另一個不為null時返回false
當兩個都不為空但是值不相等時,返回false
執(zhí)行過程:當滿足終止條件時進行返回,不滿足時分別判斷左子樹和右子樹是否相同,其中要注意代碼中的短路效應
時間復雜度:O(n),n為樹的節(jié)點個數(shù)
Java版本
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if(p == null && q == null)
return true;
if(p == null || q == null)
return false;
if(p.val != q.val)
return false;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
JavaScript版本
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} p
* @param {TreeNode} q
* @return {boolean}
*/
var isSameTree = function(p, q) {
if(p == null && q == null)
return true;
if(p == null || q == null)
return false;
if(p.val != q.val)
return false;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};
關于“LeetCode中如何解決相同的樹問題”這篇文章就分享到這里了,希望以上內(nèi)容可以對大家有一定的幫助,使各位可以學到更多知識,如果覺得文章不錯,請把它分享出去讓更多的人看到。
網(wǎng)頁標題:LeetCode中如何解決相同的樹問題
分享URL:http://muchs.cn/article14/ihcpde.html
成都網(wǎng)站建設公司_創(chuàng)新互聯(lián),為您提供全網(wǎng)營銷推廣、域名注冊、、服務器托管、企業(yè)建站、網(wǎng)站內(nèi)鏈
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請盡快告知,我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場,如需處理請聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時需注明來源: 創(chuàng)新互聯(lián)