Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

I. Title Description:

100. Same Tree – Force Buckle (LeetCode) (leetcode-cn.com)

Given the root nodes p and q of two binary trees, write a function to check whether the two trees are the same.

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

 

Example 1:

Input: p = [1,2,3], q = [1,2,3] output: trueCopy the code

Example 2:

Input: p = [1,2], q = [1, NULL,2] Output: falseCopy the code

Example 3:

Input: p = [1,2,1], q = [1,1,2] output: falseCopy the code

Tip:

  • The number of nodes in both trees is within the range [0, 100]
  • -10^4 <= Node.val <= 10^4

Ii. Analysis of Ideas:

There are only two ways for two trees to be equal:

1. All are empty trees.

2. Their root nodes are equal, and their left and right subtrees are equal. Other cases are necessarily different.

Iii. AC Code:

func isSameTree(p *TreeNode, q *TreeNode) bool {
    switch {
        case p == q && p == nil:
            return true
        casep ! =nil&& q ! =nil:
            return p.Val == q.Val && isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
        default:
            return false}}Copy the code

Iv. Summary:

When encountering a tree, we usually use recursion:

  1. It’s a recursion to the left, recursion to the right, and the end condition is as long as the values are not equal, I don’t need to recurse, I just return
  2. If one tree runs out to the same depth and the other does not, false can be returned
  3. Return true if both are completed

【 范文 】

Draw solution algorithm: 100. Same tree – Same Tree – Force buckle (LeetCode) (leetcode-cn.com)