建站
咨询
售后
建站咨询
LeetCode中如何解决相同的树问题
这篇文章将为大家详细讲解有关LeetCode中如何解决相同的树问题，小编觉得挺实用的，因此分享给大家做个参考，希望大家阅读完这篇文章后可以有所收获。
成都做网站、网站设计服务团队是一支充满着热情的团队，执着、敏锐、追求更好，是创新互联的标准与要求，同时竭诚为客户提供服务是我们的理念。成都创新互联把每个网站当做一个产品来开发，精雕细琢，追求一名工匠心中的细致，我们更用心！
题目链接
https://leetcode-cn.com/problems/same-tree/
题目描述
给定两个二叉树，编写一个函数来检验它们是否相同。
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 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
解题方案
思路
标签：深度优先遍历
终止条件与返回值：
当两棵树的当前节点都为null时返回true
当其中一个为null另一个不为null时返回false
当两个都不为空但是值不相等时，返回false
执行过程：当满足终止条件时进行返回，不满足时分别判断左子树和右子树是否相同，其中要注意代码中的短路效应
时间复杂度：O(n)，n为树的节点个数
代码
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中如何解决相同的树问题”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，使各位可以学到更多知识，如果觉得文章不错，请把它分享出去让更多的人看到。
网站题目：LeetCode中如何解决相同的树问题
分享链接：http://lswzjz.com/article/ihcpde.html
