《剑指Offer》-26.树的子结构

题干

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

class TreeNode{
    double value;
    TreeNode left;
    TreeNode right;
}

二叉树A

graph TD
6-->8
8-->9
6-->7
8-->2
2-->4
4-->5

二叉树B

graph TD
8-->9
8-->2

解题思路

获取B的根节点，遍历A中是否存在等于B的根节点的节点，不存在，则返回false， 存在则判断该节点的子树是否与B的结构相同，相同则返回true，不同则继续查找下一个与B的根节点相同的节点，重复上面的操作。

代码实现

<?php

class TreeNode
{
    private $val;
    private $left;
    private $right;

    public function __set($name, $value)
    {
        $this->$name = $value;
    }

    public function __get($name)
    {
        return $this->$name;
    }
}

function getTree1()
{
    $node1 = new TreeNode();
    $node1->val = 6;
    $node2 = new TreeNode();
    $node2->val = 7;
    $node3 = new TreeNode();
    $node3->val = 8;
    $node1->left = $node2;
    $node1->right = $node3;
    $node4 = new TreeNode();
    $node4->val = 2;
    $node5 = new TreeNode();
    $node5->val = 9;
    $node3->left = $node4;
    $node3->right = $node5;
    $node6 = new TreeNode();
    $node6->val = 4;
    $node4->left = $node6;
    $node7 = new TreeNode();
    $node7->val = 5;
    $node6->left = $node7;

    return $node1;
}

function getTree2()
{
    $node1 = new TreeNode();
    $node1->val = 8;
    $node2 = new TreeNode();
    $node2->val = 2;
    $node3 = new TreeNode();
    $node3->val = 9;
    $node1->left = $node2;
    $node1->right = $node3;

    return $node1;
}

function hasSubTree($tree1, $tree2)
{
    $result = false;
    if ($tree1 != null && $tree2 != null) {
        if (isEqual($tree1->val, $tree2->val)) {
            $result = doesTree1HaveTree2($tree1, $tree2);
        }
        if (!$result) {
            $result = hasSubTree($tree1->left, $tree2);
        }
        if (!$result) {
            $result = hasSubTree($tree1->right, $tree2);
        }
    }

    return $result;
}

function isEqual($val1, $val2)
{
    return ($val1 - $val2 > -10e-7) && ($val1 - $val2 < 10e-7);
}

function doesTree1HaveTree2($tree1, $tree2)
{
    if ($tree2 == null) {
        return true;
    }
    if ($tree1 == null) {
        return false;
    }
    if (!isEqual($tree1->val, $tree2->val)) {
        return false;
    }

    return doesTree1HaveTree2($tree1->left, $tree2->left) && doesTree1HaveTree2($tree1->right, $tree2->right);
}

$tree1 = getTree1();
$tree2 = getTree2();
var_dump(hasSubTree($tree1, $tree2));