100. Same Tree

題目

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Example 1:

Input: p = [1,2,3], q = [1,2,3] Output: true

Example 2:

Input: p = [1,2], q = [1,null,2] Output: false

Example 3:

Input: p = [1,2,1], q = [1,1,2] Output: false

Constraints:

The number of nodes in both trees is in the range [0, 100]. -104 <= Node.val <= 104

• Accepted: 1.8M
• Submissions: 3.1M
• Acceptance Rate: 60.3%

題目大意

判斷 2 顆樹是否是完全相等的

解題思路

遞歸判斷即可

Big O

時間複雜 : O(n) 空間複雜 : O(1)

來源

• https://leetcode.com/problems/same-tree/
• https://leetcode.cn/problems/same-tree/
• https://books.halfrost.com/leetcode/ChapterFour/0100~0199/0100.Same-Tree/

解答

https://github.com/kimi0230/LeetcodeGolang/blob/master/Leetcode/0100.Same-Tree/main.go

package sametree

import "LeetcodeGolang/structures"

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */

type TreeNode = structures.TreeNode

// 時間複雜 O(n), 空間複雜 O(1)
func IsSameTree(p *TreeNode, q *TreeNode) bool {
    if p == nil && q == nil {
        return true
    } else if p != nil && q != nil {
        if p.Val == q.Val {
            return IsSameTree(p.Left, q.Left) && IsSameTree(p.Right, q.Right)
        }
        return false
    } else {
        return false
    }
}

Benchmark