PHP 一个树为另一棵树的子结构 [TO BE CONTINUED]

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

 　　

<?php
class TreeNode {
    private $val;
    private $left;
    private $right;

    public function __construct($val=null, $left = null, $right = null) {
        $this->val = $val;
        $this->left = $left;
        $this->right = $right;
    }

    /**
     * @param $x : val
     * @param $t TreeNode or: null
     */
    public function insert($x) {
        if ($this->val ===null) {
            $this->val = $x;
        }
        if ($x < $this->val) {
            $this->left = is_null($this->left) ? new self($x) :
                $this->left->insert($x);
        } else if ($x > $this->val) {
            $this->right = is_null($this->right) ? new self($x):
                $this->right->insert($x);
        }
        /* else x is in the tree already; we'll do nothing */
        return $this;
    }

    /**
     * 先序遍历
     * @param $callback
     */
    public function traversePre($callback) {
        if (is_null($this->val)) {
            return;
        }
        call_user_func($callback, $this->val);
        if (!is_null($this->left)) {
            $this->left->traversePre($callback);
        }
        if (!is_null($this->right)) {
            $this->right->traversePre($callback);
        }
    }

    /**
     * 中序遍历
     * @param $callback
     */
    public function traverseMid($callback) {
        if (is_null($this->val)) {
            return;
        }
        if (!is_null($this->left)) {
            $this->left->traverseMid($callback);
        }
        call_user_func($callback, $this->val);
        if (!is_null($this->right)) {
            $this->right->traverseMid($callback);
        }
    }

    /**
     * @return null
     */
    public function makeEmpty() {
        if ($this->left !== null) {
            $this->left->makeEmpty();
            unset($this->left);
        }
        if ($this->right !== null) {
            $this->right->makeEmpty();
            unset($this->right);
        }
        $this->val = null;
        return null;
    }

    /**
     * fixme: find(7) => find(11)?
     * @return null
     */
    public function find($x) {
        if ($this->val===null) {
            return null;
        }
        return ($x < $this->val) ? (is_null($this->left) ? null : $this->left->find($x)) :
            ($x > $this->val) ? (is_null($this->right) ? null: $this->right->find($x)) : $this;
    }

    /**
     * 输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
     * @param $pRoot1
     * @param $pRoot2
     * @return bool
     */
    public static function HasSubtree($pRoot1, $pRoot2) {
        if ($pRoot2 === null || $pRoot1===null) {
            return false;
        }
        if ($pRoot1->val===$pRoot2->val) {
            return self::isSubTree($pRoot1, $pRoot2) ||
            self::isSubTree($pRoot1->left, $pRoot2) || self::isSubTree($pRoot1->right, $pRoot2);
        }
        return false;
    }

    private static function isSubTree($root1, $root2) {
        if ($root2===null) {return true;}
        if ($root1 === null) {return false;}
        if ($root1->val === $root2->val) {
            return self::isSubTree($root1->left, $root2->left) && self::isSubTree($root1->right, $root2->right);
        }
        return false;
    }

}

　　

test:

/**
    8
  /  
 6   10
/   / 
5  7 9 11
*/

$tree = new TreeNode();

$a = [8,6,10,5,7,9,11];
array_walk($a, function($value, $index, $tree) {
    $tree->insert($value);
}, $tree);

$tree->traversePre(function($elem) {echo $elem.',';});
echo PHP_EOL;
$tree->traverseMid(function($elem) {echo $elem.',';});
echo PHP_EOL;
var_dump($tree->find(7));
// $tree->makeEmpty();