[剑指offer][JAVA]面试题第[26]题[树的子结构][递归]

刺骨的言语ヽ痛彻心扉 2023-02-18 05:29 42阅读 0赞

#### 【问题描述】\[中等\] ####

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
    
    B是A的子结构， 即 A中有出现和B相同的结构和节点值。
    
    例如:
    给定的树 A:
    
         3
        / \
       4   5
      / \
     1   2
    给定的树 B：
    
       4 
      /
     1
    返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。
    
    示例 1：
    
    输入：A = [1,2,3], B = [3,1]
    输出：false
    示例 2：
    
    输入：A = [3,4,5,1,2], B = [4,1]
    输出：true
    限制：
    
    0 <= 节点个数 <= 10000

#### 【解答思路】 ####

###### 1. 递归思路一 ######

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

class Solution { 
        public boolean isSubStructure(TreeNode A, TreeNode B) { 
            return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
        }
        boolean recur(TreeNode A, TreeNode B) { 
            if(B == null) return true;
            if(A == null || A.val != B.val) return false;
            return recur(A.left, B.left) && recur(A.right, B.right);
        }
    }

###### 2. 递归思路二 ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]

class Solution { 
        public boolean isSubStructure(TreeNode A, TreeNode B) { 
            if(A== null || B == null)return false;
           return fun(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B);
    
        }
        public boolean fun(TreeNode a,TreeNode b){ 
            if(b == null) return true;
            if(a == null) return false;
            return (a.val == b.val) && fun(a.left,b.left) && fun(a.right,b.right);
        }
    }

#### 【总结】 ####

###### 1.树的问题 递归思想很重要 切分子问题 ######

###### 2.想清楚边界问题 ######

转载链接：https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/solution/mian-shi-ti-26-shu-de-zi-jie-gou-xian-xu-bian-li-p/  
转载链接:https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/solution/di-gui-by-rich/

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200616105232778.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[20200616105255145.png]: https://img-blog.csdnimg.cn/20200616105255145.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200616105325221.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70