面试题26:树的子结构

题目

输入两颗二叉树A和B，判断B是不是A的子结构。二叉树的节点定义如下:

struct BinaryTreeNode{
    double             val;
    BinaryTreeNode* left;
    BinaryTreeNode* right;
};

image.png

解题思路

1. 在树A中找出和树B的根节点的值一样的节点R
2. 判断树A中以R为根节点的子树是不是包含和树B一样的结构

代码

• 细节
  1)定义函数DoesTree1HaveTree2来判断两个子树的节点值是否相同

2. 在判断两个节点值是否相等时，因为节点中值类型为double,所以不能直接写root1->val = root2->val，只能判断它们之差的绝对值在一个很小的范围内。

class Solution{
    public:
        bool Equal(double a,double b)
        {
            if((a-b > -0.000001) && (a-b < 0.000001))
            {
                return true;
            }
            else
            {
                return false;
            }
        }
        bool DoesTree1HaveTree2(BinaryTreeNode* root1,BinaryTreeNode* root2)
        {
            if(root2 == NULL) return true;
            if(root1 == NULL) return false;
            if(!Equal(root1->val,root2->val))
            {
                return false;
            }
            return DoesTree1HaveTree2(root1->left,root2->left) && DoesTree1HaveTree2(root1->right,root2->right);
        }
        
        bool hasSubtree(BinaryTreeNode *root1,BinaryTreeNode *root2)
        {
            bool result = false;
            if(root1!= NULL && root2 != NULL)
            {
                //A树中节点值和B树中节点值相同
                if(Equal(root1->val,root2->val))
                {
                    result = DoesTree1HaveTree2(root1,root2);
                }
                if(!result)
                {
                    result = hasSubtree(root1->left,root2);
                }
                if(!result)
                {
                    result = hasSubtree(root1->right,root2);
                }
            }
            return result;
        }
};

完整代码见Github，看到这篇一定要点开这里哦，一定不会让你失望的，代码从头文件到main()都补充完整了~~~