JavaScript版《剑指offer》刷题（16）树的子结构

╰半夏微凉° 2022-01-12 08:07 133阅读 0赞

**1.题目描述**

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

**2.思路**

二叉树子结构的意思是包含了一个结点，可以只取左子树或者右子树，或者都不取。例如：

![在这里插入图片描述][20190621151228396.png]

由于A中有一部分子树的结构和B是一样的，因此B是A的子结构。

思路：  
1.有关二叉树的算法问题，一般都可以通过递归来解决。那么写成一个正确的递归程序，首先一定要分析正确递归结束的条件。  
2.如果根节点相同则递归调用isSubtree（），如果根节点不相同，则判断root1的左子树和root2是否相同，再判断右子树和tree2是否相同;  
3.注意null的条件，HasSubTree中，如果两棵树都不为空才进行判断，isSubtree中，如果root2为空，则说明第二棵树遍历完了，即匹配成功;  
4.root1为空有两种情况：（1）如果root1为空&&root2不为空说明不匹配，（2）如果root1为空，root2为空，说明匹配。

分析如何判断树B是不是树A的子结构，只需要两步。很容易看出来这是一个递归的过程。一般在树的求解方面都和递归有关。  
Step1.在树A中找到和B的根结点的值一样的结点R；  
Step2.判断树A中以R为根结点的子树是不是包含和树B一样的结点。

**3.代码**

/* function TreeNode(x) {
        this.val = x;
        this.left = null;
        this.right = null;
    } */
    function isSubtree(root1, root2) {
        if (root2 == null) return true;
        if (root1 == null) return false;
        if (root1.val == root2.val) {
            return isSubtree(root1.left, root2.left) &&
                isSubtree(root1.right, root2.right);
        } else {
            return false;   
        }
    }
     
    function HasSubtree(pRoot1, pRoot2)
    {
       if (pRoot1 == null || pRoot2 == null) {
           return false;
       }
        return isSubtree(pRoot1, pRoot2) ||
            HasSubtree(pRoot1.left, pRoot2) ||
            HasSubtree(pRoot1.right, pRoot2);
    }

参考文章：  
[https://www.cnblogs.com/echovic/p/6431974.html][https_www.cnblogs.com_echovic_p_6431974.html]  
[https://www.cnblogs.com/wuguanglin/p/HasSubtree.html][https_www.cnblogs.com_wuguanglin_p_HasSubtree.html]  
[https://github.com/DavidChen93/-offer-JS-/blob/master/26.1 树的子结构.js][https_github.com_DavidChen93_-offer-JS-_blob_master_26.1 _.js]

[https://blog.csdn.net/u013309870/article/details/70049739][https_blog.csdn.net_u013309870_article_details_70049739]  
[https://blog.csdn.net/denghecsdn/article/details/78596772][https_blog.csdn.net_denghecsdn_article_details_78596772]

[20190621151228396.png]: /images/20220109/d7e8a14105864c549b573925f81e6486.png
[https_www.cnblogs.com_echovic_p_6431974.html]: https://www.cnblogs.com/echovic/p/6431974.html
[https_www.cnblogs.com_wuguanglin_p_HasSubtree.html]: https://www.cnblogs.com/wuguanglin/p/HasSubtree.html
[https_github.com_DavidChen93_-offer-JS-_blob_master_26.1 _.js]: https://github.com/DavidChen93/-offer-JS-/blob/master/26.1%20%E6%A0%91%E7%9A%84%E5%AD%90%E7%BB%93%E6%9E%84.js
[https_blog.csdn.net_u013309870_article_details_70049739]: https://blog.csdn.net/u013309870/article/details/70049739
[https_blog.csdn.net_denghecsdn_article_details_78596772]: https://blog.csdn.net/denghecsdn/article/details/78596772