LeetCode_二叉树_中等_剑指 Offer 26.树的子结构

缺乏、安全感 2023-10-09 20:32 24阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

入两棵二叉树 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

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/shu-de-zi-jie-gou-lcof

## 2.思路 ##

（1）前序遍历  
思路参考[该 LeetCode 用户题解][LeetCode]。

## 3.代码实现（Java） ##

//思路1————前序遍历
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        
        public boolean isSubStructure(TreeNode A, TreeNode B) {
        
            if (A == null || B == null) {
        
                return false;
            }
            return backtrack(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
        }
    
        public boolean backtrack(TreeNode A, TreeNode B) {
        
            if (B == null) {
        
                return true;
            }
            if (A == null || A.val != B.val) {
        
                return false;
            }
            return backtrack(A.left, B.left) && backtrack(A.right, B.right);
        }
    }

[LeetCode]: https://leetcode.cn/problems/shu-de-zi-jie-gou-lcof/solution/mian-shi-ti-26-shu-de-zi-jie-gou-xian-xu-bian-li-p/