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中如何解决相同的树问题

LeetCode中如何解决相同的树问题

关于“LeetCode中如何解决相同的树问题”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,使各位可以学到更多知识,如果觉得文章不错,请把它分享出去让更多的人看到。


标题名称:LeetCode中如何解决相同的树问题
网页网址:http://hbruida.cn/article/ihcpde.html