个人中心
gpt4 book ai didi

100. Same Tree 相同的树

转载 作者：大佬之路 更新时间：2024-01-31 14:21:43 25 4
gpt4 key购买 nike

题目地址：https://leetcode.com/problems/same-tree/open in new window

Total Accepted: 126017 Total Submissions: 291619 Difficulty: Easy

题目描述

Given two binary trees, write a function to check if they are the same or not.

Twobinary trees are considered the same if they are structurally identical and the nodes have the same value.

Example 1:

Input:     1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

Output: true

Example 2:

Input:     1         1
          /           \
         2             2

        [1,2],     [1,null,2]

Output: false

Example 3:

Input:     1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

Output: false

题目大意

判断两棵二叉树是否完全相等。

解题方法

这道题是树的题目，属于最基本的树遍历的问题。

问题要求就是判断两个树是不是一样，基于先序，中序或者后序遍历都可以做完成，因为对遍历顺序没有要求。

这里我们主要考虑一下结束条件，如果两个结点都是null，也就是到头了，那么返回true。如果其中一个是null，说明在一棵树上结点到头，另一棵树结点还没结束，即树不相同，或者两个结点都非空，并且结点值不相同，返回false。最后递归处理两个结点的左右子树，返回左右子树递归的与结果即可。

这里使用的是先序遍历，算法的复杂度跟遍历是一致的，如果使用递归，时间复杂度是O(n)，空间复杂度是O(logn)。代码如下：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null && q==null){
            return true;
        }
        if(p==null || q==null){//注意是在p/q都不为空的情况下有一个为空，说明另外一个不为空
            return false;
        }
        if(p.val!=q.val){//注意是不相等返回False，相等的话需要继续进行子节点的判断
            return false;
        }
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
}

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

AC:0ms

递归问题最终要的是终止条件！！！一定要万无一失。二刷，python。

两年前的我竟然写了这么多啊，现在写一个Python版本的。

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def isSameTree(self, p, q):
        """
        :type p: TreeNode
        :type q: TreeNode
        :rtype: bool
        """
        if not p and not q:
            return True
        if not p or not q:
            return False
        return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有

本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发

25 4 0
文章推荐： 129. Sum Root to Leaf Numbers 求根节点到叶节点数字之和
文章推荐： 229. Majority Element II 多数元素 II
文章推荐： 226. Invert Binary Tree 翻转二叉树
文章推荐： 145. Binary Tree Postorder Traversal 二叉树的后序遍历
大佬之路
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com