集团网站建设方案网站注册

Problem: 100. 相同的树

题目描述

思路

题目要求判断两个二叉树是否完全相同，而此要求可以利用问题分解的思想解决，即判断当前节点的左右子树是否完全相同，而在二叉树问题分解的一般题目中均会带有返回值，具体的此题中当p、q指针均为null时返回true，当其中一个为null时（不是同时为null）返回false，当p、q指针指向的节点值不相同时返回false。

时间复杂度:

$O(n)$;其中$n$为二叉树的节点个数

空间复杂度:

$O(h)$；其中$h$为二叉树的高度

Code

class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {if (p == null && q == null) {return true;}if (p == null || q == null) {return false;}if (p.val != q.val) {return false;}//Check whether the left and right subtrees are the samereturn isSameTree(p.left, q.left) && isSameTree(p.right, q.right);}
}