微信公众号：路人zhang
扫码关注微信公众号

回复“面试手册”，获取本站PDF版

回复“简历”，获取高质量简历模板

回复“加群”，加入程序员交流群

回复“电子书”，获取程序员类电子书

当前位置： 算法 > 剑指offer > 剑指offer 26.树的子结构

剑指offer 26.树的子结构

题目描述

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

题解

(DFS,暴力遍历) O(nm)

算法步骤：

  1. 遍历树 root 中的每个节点 s 都与子树 subRoot 进行匹配
  2. 递归匹配子树 s 和 subRoot 中的每个节点，如果每个节点都相同，则匹配成功。

边界：

  1. 在 isSubStructure() 中如果 subRoot 为空，题目已知空树不是任何树的子结构，所以返回 false。
  2. 在 dfs() 中，当 q 为空时不需要判断 p 是否为空，只要保证 q 是 p 的子结构即可，不需要完全匹配。

时间复杂度

树 root 中的每个节点都需要与子树 subRoot 进行匹配，所以时间复杂度为 O(nm)，n 为 root 的节点个数，m 为 subRoot 的节点个数。

空间复杂度

一次匹配时最多需要 O(max(d_1, d_2)) 的空间复杂度，d_1 表示 root 的子树匹配结束时的深度，d_2 表示 subRoot 匹配结束时的深度。

C++ 代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool dfs(TreeNode* p, TreeNode* q) {
        if (!q) return true;
        if (!p || p->val != q->val) return false;
        return dfs(p->left, q->left) && dfs(p->right, q->right);
    }

    bool isSubStructure(TreeNode* root, TreeNode* subRoot) {
        if (!root || !subRoot) return false;
        if (dfs(root, subRoot)) return true;
        return isSubStructure(root->left, subRoot) || isSubStructure(root->right, subRoot);
    }
};

Java 代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean dfs(TreeNode p, TreeNode q) {
        if (q == null) {
            return true;
        }
        if (p == null || p.val != q.val) {
            return false;
        }
        return dfs(p.left, q.left) && dfs(p.right, q.right);
    }

    public boolean isSubStructure(TreeNode root, TreeNode subRoot) {
        if (root == null || subRoot == null) {
            return false;
        }
        if (dfs(root, subRoot)) {
            return true;
        }
        return isSubStructure(root.left, subRoot) || isSubStructure(root.right, subRoot);
    }
}

Python 代码

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def dfs(self, p: TreeNode, q: TreeNode) -> bool:
        if not q:
            return True
        if not p or p.val != q.val:
            return False
        return self.dfs(p.left, q.left) and self.dfs(p.right, q.right)

    def isSubStructure(self, root: TreeNode, subRoot: TreeNode) -> bool:
        if not root or not subRoot:
            return False
        if self.dfs(root, subRoot):
            return True
        return self.isSubStructure(root.left, subRoot) or self.isSubStructure(root.right, subRoot)

本文由读者提供，Github地址：https://github.com/tonngw

点击面试手册，获取本站面试手册PDF完整版

剑指offer