刷题leetcode100 SameTree

Myth丶恋晨 2021-10-09 03:46 387阅读 0赞

2018.1.7加油！！![生气][mad.gif]

Given two binary trees, 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:     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

题目意思：就是比较两个树是不是完全一样，包括顺序、数值。任何不一样都要返回false. 当前结点的val相等，就递归比较p的左子树和q的左子树，p的右子树和q的右子树，同时相等才能返回true,否则返回false

知识点：

(1)递归，return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);

递归的过程取的是子节点， 逐渐缩小树的范围，最后相当于到叶子了。

（2）二叉树的取值方式，p.val,p.left,p.right,

解法2：

public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null && q==null) return true;
        if(p==null || q==null) return false;
        return (p.val==q.val) && isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }

解法1：

解法1：/**
     * 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; //两个空树，返回true
           if(p==null || q== null) return false;//有一个空的，返回false
           if(p.val == q.val){  //当前val相等，递归比较子节点（左右子树同时的结果）
               return  isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
           }
            return false;
           
        }
    }

[mad.gif]: /images/20211009/16611aa7c84544ef9c8dc06d8f00b419.png