JavaScript实现树的子结构

写在前面
这是鄙人昨天遇到的一道笔试题，思考了好半天总算是做了出来。今天翻《剑指Offer》时，赫然看了这道题目，不禁佩服作者的逻辑性之强。虽然我们的实现方法大体一致，但我考虑的还不是很全面，代码也写的不够简洁，看来我等还需要好好修炼内功呀。

题目描述

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

实现思路

首先，使用先序遍历遍历A树，在A树中找到和B树根节点值相同的结点。
然后使用先序遍历+递归来判断B树中的结点是不是在A树中。不要忘了递归的结束条件：如果B树中的结点空了，就返回true。如果是A树中的结点为null，则返回false。

JavaScript代码实现

function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} 
function HasSubtree(pRoot1, pRoot2)
{
    var res = false;
    if(pRoot1 && pRoot2) {
        if(pRoot1.val === pRoot2.val) {
            res = DoesTree1HavaTree2(pRoot1, pRoot2);
        }
        if(!res) {
            res = HasSubtree(pRoot1.left, pRoot2) ||  HasSubtree(pRoot1.right, pRoot2);
        }
    }
    return res;
}
function DoesTree1HavaTree2(pRoot1, pRoot2) {
    if(!pRoot2) {
        return true;
    }
    if(!pRoot1) {
        return false;
    }
    if(pRoot1.val !== pRoot2.val) {
        return false;
    }
    return DoesTree1HavaTree2(pRoot1.left, pRoot2.left) && DoesTree1HavaTree2(pRoot1.right, pRoot2.right);
}
module.exports = {
    HasSubtree : HasSubtree
};