相同的树
-
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
-
如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
示例 1：
输入： p = [1,2,3], q = [1,2,3]
输出：true
解题思路
- 比较当前节点的值是否相等。
- 递归比较左子树。
- 递归比较右子树。
- 如果当前节点值相等，且左子树和右子树递归比较结果都为 true，则当前子树相同；否则不同。
Java实现
public class SameTree {public static class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }}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;}// 递归比较左子树和右子树return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);}public static void main(String[] args) {SameTree solution = new SameTree();// 创建两个示例树TreeNode p = new TreeNode(1);p.left = new TreeNode(2);p.right = new TreeNode(3);TreeNode q = new TreeNode(1);q.left = new TreeNode(2);q.right = new TreeNode(3);System.out.println(solution.isSameTree(p, q)); // 输出: true// 创建两个不同的树TreeNode r = new TreeNode(1);r.left = new TreeNode(2);TreeNode s = new TreeNode(1);s.right = new TreeNode(2);System.out.println(solution.isSameTree(r, s)); // 输出: false}
}时间空间复杂度
- 时间复杂度: O(n)，其中 n 是两棵树中节点的数量。需要遍历每个节点来进行比较。
- 空间复杂度: O(h)，其中 h 是树的高度。由于递归调用栈的深度等于树的高度，最坏情况下（完全不平衡的树）递归栈的深度等于 n（节点数）。
