100. 相同的树

image.png
image.png

递归，把问题转化为找不同

  1. class Solution {
  3.     // 把思路转化为判断两个树是否存在不同的节点
  4.     public boolean isSameTree(TreeNode p, TreeNode q) {
  6.         // 如果两颗树都为空：1. 测试用例是两颗空树，2. 深度优先搜索到底了没有发现不同的元素
  7.         // 说明两颗树相同，返回 true
  8.         if (p == null && q == null) return true;
  10.         // 如果其中一颗树为空说明深度搜索过程中树结构不同
  11.         // 说明两颗树不相同，返回 false
  12.         if (p == null || q == null) return false;
  14.         // 如果两颗树的根节点值不同，返回 false
  15.         if (p.val != q.val) return false;
  17.         // 递归对比左子树与右子树
  18.         return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
  19.     }
  20. }