LeetCode100-Same Tree

题目

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

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

分析

递归法求解。既然要判断两棵树是否相同,我们可以同步地遍历这两棵树,边在遍历的时候先序访问根元素,看他们是否相等,而相等有两种情况:

  • 两棵树均为空。说明到达树的尾部(递归出口)了,返回true。
  • 两棵树均不为空,且值相等。但此时并不能立即返回,因为光是当前根节点相等了并不代表剩余的节点就相等,所以需要继续分别遍历左子树+右子树,他们对应相等了(即都返回true了)才能最终返回true。

其余情况一概说明两棵树在从这个节点上不相等,立即返回false。

代码

public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        
        //两者均为指向空
        if (p == null && q == null) return true;
        
        //两者均不为空,且值相等
        else if (p != null && q != null && p.val == q.val) return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        
        //两者其一为空,其一不为空,或值不相等
        else return false;
    }
}

 

Leave a Comment.