Leetcode 572 Subtree of Another Tree 题解分析

发表于 分类于 ， 阅读次数： 阅读次数： Disqus：

题目介绍

Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.

A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node’s descendants. The tree tree could also be considered as a subtree of itself.

示例 1

Input: root = [3,4,5,1,2], subRoot = [4,1,2]
Output: true

示例 2

Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
Output: false

解析

需要判断subRoot 为根节点的这棵树是不是 root 为根节点的这个树的子树，题应该不是特别难理解，只是需要注意，这里是子树，而不是一个子结构，也就是示例 2 的判断结果是 false，因为左边子树还有个 0，只能认为是左边的一部分，但不是子树，思路分析也不难，就是递归去判断，只不过是两种维度，第一种就是找到子树的根节点，也就是在 root 树找到 subRoot 的根节点相同的节点，这个就会用到递归，如果找到了一个，就开始递归的对比所有子节点，必须完全一样

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public boolean isSubtree(TreeNode root, TreeNode subRoot) {
       if (subRoot == null || root == null) {
           return false;
       }
       if (root.val == subRoot.val) {
           // 如果 root 节点跟 subRoot 节点相同，就开始递归对比所有的子节点
           if (isSameTree(root.left, subRoot.left) && isSameTree(root.right, subRoot.right)) {
               return true;
           }
       }
       // 如果 root 节点不同，就开始递归往下找与 subRoot 相同的起始节点，这里是或的关系，因为在左右子树任一找到一个就行
       return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
   }
   // 需要完全相同，也就是说不能像示例 2 那样多一个子节点这种，以及其他不同的情况，反正就是要完全一样
   public boolean isSameTree(TreeNode root, TreeNode subTree) {
       // 如果递归到这个节点都为空也认为是相同的
       if (root == null && subTree == null) {
           return true;
       }
       // 因为有前面的判断，这里就隐含了 subTree != null 这个条件
       if (root == null) {
           return false;
       }
       // 也因为有前面的判断，这里就隐含了  root != null 这个条件
       if (subTree == null) {
           return false;
       }
       // 两个都不为空，但是值不相同，也是 false
       if (root.val != subTree.val) {
           return false;
       }
       // 跟节点相同，就开始递归判断左右子树，必须两者都相同
       return isSameTree(root.left, subTree.left) && isSameTree(root.right, subTree.right);
   }