判断一棵树是否是另一棵树的子树

题目：判断一棵树是否是另一棵树的子树（两棵树均是有序的，即树的左右子树的顺序是固定的）

分析：假设这两棵树中的第一棵为母树，另一棵为子树。首先在母树中搜索子树的根节点，找到根节点之后就按照该根节点向下搜索比较，如果比较结果为true即子树是母树的一棵子树，否则的话继续向下搜索子树根节点在母树中的位置，如此递归下去最终即可得到结果。

按照下面的例子

代码如下：

package problem2;
/**
 * @author Hutongling
 */
class TreeNode{
int value;
    TreeNode leftChild=null;
    TreeNode rightChild=null;
    TreeNode() {}
    TreeNode(int value){
this.value=value;
    }
    TreeNode(int value,TreeNode leftChild,TreeNode rightChild){
this.value=value;
this.leftChild=leftChild;
this.rightChild=rightChild;
    }
public int getValue() {
return value;
    }
public void setValue(int value) {
this.value = value;
    }
public TreeNode getLeftChild() {
return leftChild;
    }
public TreeNode getRightChild() {
return rightChild;
    }
public void setLeftChild(TreeNode leftChild) {
this.leftChild = leftChild;
    }
public void setRightChild(TreeNode rightChild) {
this.rightChild = rightChild;
    }
}
public class 树的子结构 {

// 搜索子树的根节点在母树中的节点的位置,并检查是否相等
static boolean searchParentForChildRoot(TreeNode parentRoot, TreeNode childRoot) {
boolean result = false;
if (parentRoot != null && childRoot != null) {
if (childRoot.getValue() == parentRoot.getValue()) 
                result=compareParentAndChildTree(parentRoot,childRoot);
if(!result)
                result=compareParentAndChildTree(parentRoot.getLeftChild(),childRoot);
if(!result)
                result=compareParentAndChildTree(parentRoot.getRightChild(), childRoot);
        }
return result;
    }

// 比较以得到的和子树根节点相同的节点的子树和原始子树，若相同则返回true，否则返回false
static boolean compareParentAndChildTree(TreeNode parentRoot, TreeNode childRoot) {
if (childRoot == null)// 结束条件为子树节点为空
return true;
if (parentRoot == null)
return false;
if (childRoot.getValue() != parentRoot.getValue()) {
return false;
        } else 
return compareParentAndChildTree(parentRoot.getLeftChild(), childRoot.getLeftChild()) == true&& compareParentAndChildTree(parentRoot.getRightChild(), childRoot.getRightChild()) == true;
    }

//static boolean childTree
public static void main(String[] args) {
        TreeNode paremtRoot=new TreeNode(8);
        TreeNode rootChild1=new TreeNode(8);
        TreeNode rootChild2=new TreeNode(7);
        TreeNode child1Child1=new TreeNode(9);
        TreeNode child1Child2=new TreeNode(2);
        TreeNode child12Child1=new TreeNode(4);
        TreeNode child12Child2=new TreeNode(7);

        paremtRoot.setLeftChild(rootChild1);
        paremtRoot.setRightChild(rootChild2);
        rootChild1.setLeftChild(child1Child1);
        rootChild1.setRightChild(child1Child2);
        child1Child2.setLeftChild(child12Child1);
        child1Child2.setRightChild(child12Child2);

        TreeNode childRoot=new TreeNode(8);
        TreeNode crootChild1=new TreeNode(9);
        TreeNode crootChild2=new TreeNode(2);
        childRoot.setLeftChild(crootChild1);
        childRoot.setRightChild(crootChild2);

        System.out.println(searchParentForChildRoot(paremtRoot,childRoot));
    }

}

其代码的结果为：true