首页 > 其他 > 详细

【剑指Offer-26】树的子结构

时间:2021-02-18 23:23:09      阅读:32      评论:0      收藏:0      [点我收藏+]

问题

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

B是A的子结构, 即 A中有出现和B相同的结构和节点值。

例如:
给定的树A与树B:

技术分享图片
返回 true,因为 B 与 A 的一个子树拥有相同的结构和节点值。 ```cpp // Definition for a binary tree node. struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; ``` ## 示例 > **输入:** A = [1,2,3], B = [3,1] **输出:** false > > 输入:A = [3,4,5,1,2], B = [4,1] 输出:true

解答

class Solution {
public:
    bool isSubStructure(TreeNode* A, TreeNode* B) {
        return ((A && B) && (recur(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B)));
    }
private:
    bool recur(TreeNode* A, TreeNode* B) {
        if (!B)
            return true;
        if (!A || A->val != B->val)
            return false;
        return (recur(A->left, B->left) && recur(A->right, B->right));
    }
};

重点思路

这道题虽然有两个递归,看起来很复杂,但是这两个递归都是用于遍历的,非常容易理解。具体遍历过程如下图所示。这里着重讨论一下几个重要语句的作用。

技术分享图片

recur(A, B) || isSubStructure(A->left, B) || isSubStructure(A->right, B))这一句首先使用recur函数判断根节点为B的树是否是根节点为A的树的子树。具体判断方法为:

  • 当B节点为空时,表示B已检查完毕,符合子树要求,返回true
  • 当A节点为空时,表示B没有包含在A中,返回false
  • 当A与B节点值不相同时,返回false
  • 当B的左右子树都满足要求时,recur函数返回true

recur(A, B)返回true时,由于||具有截断性,所以上一条语句直接返回true;如果recur返回false,即匹配失败时,则继续对A做前序遍历,即isSubStructure(A->left, B) || isSubStructure(A->right, B),A前序遍历的终止条件为A && B

【剑指Offer-26】树的子结构

原文:https://www.cnblogs.com/tmpUser/p/14413748.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!