剑指 Offer 26. 树的子结构

题目描述

输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

输入输出

1
2
3
4
5
6
7
8
9
10
11
   1
  / \
 2   3
   3
  /
 1
输入：A = [1,2,3], B = [3,1]
输出：false

输入：A = [3,4,5,1,2], B = [4,1]
输出：true

基本思路

recur(A, B)

  1. 终止条件
    1. B为空：说明B匹配完成（越过叶子节点），返回true
    2. A为空：说明越过A叶子节点匹配失败，返回false
    3. A的值与B的值不相等，说明匹配失败，返回false
  2. 返回值
    1. 判断A和B的左子节点是否相等
    2. 判断A和B的右子节点是否相等

isSubStructure(A, B)

  1. 特例处理：当A 或 B为空时返回false
  2. 返回值
    1. A中包含B
    2. B是A的左子树的子结构
    3. B是A的右子树的子结构

java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * 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 (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);
    }
}