[游戏开发]输入两个二叉树A 和B，判断B 是不是A 的子结构

题目

• 输入两个二叉树A 和B，判断B 是不是A 的子结构

解法

• 构建二叉树

public class BSTNode<T extends Comparable<T>> {
    T key;
    BSTNode<T> left;
    BSTNode<T> right;
    BSTNode<T> parent;

    public BSTNode(T key, BSTNode<T> parent, BSTNode<T> left, BSTNode<T> right) {
        this.key = key;
        this.parent = parent;
        this.left = left;
        this.right = right;
    }
}

• 判断是否包含子树根结点

 public static boolean hasChildTree(BSTNode parent, BSTNode childTree) {
        boolean hasChildTree = false;
        if (parent != null && childTree != null) {
            // 根结点
            if (parent.key == childTree.key) {
                hasChildTree = isChildTree(parent, childTree);
            }

            // 左子树
            if (!hasChildTree) {
                hasChildTree = isChildTree(parent.left, childTree);
            }

            // 右子树
            if (!hasChildTree) {
                hasChildTree = isChildTree(parent.right, childTree);
            }

        }
        return hasChildTree;
    }

• 判断是否左子树和右子树相同

  private static boolean isChildTree(BSTNode parent, BSTNode childTree) {
        if (childTree == null) return true;
        if (parent == null) return false;
        if (parent.key != childTree.key) return false;
        return isChildTree(parent.left, childTree.left) && isChildTree(parent.right, childTree.right);
    }