本题是《剑指offer》第18题。
题目：输入两棵二叉树A和B，判断B是不是A的子结构。
注意审题，子结构不是子树！
private class Node {
int value;
Node left;
Node right;
}
public boolean hasSubStructure(Node p1, Node p2) {
if (p1 == null || p2 == null) {
return false;
}
boolean result = isTree1HasTree2(p1, p2);
if (!result) {
result = isTree1HasTree2(p1.left, p2);
}
if (!result) {
result = isTree1HasTree2(p1.right, p2);
}
return result;
}
private boolean isTree1HasTree2(Node p1, Node p2) {
if (p2 == null) {
return true;
}
if (p1 == null) {
return false;
}
if (p1.value != p2.value) {
return false;
}
return isTree1HasTree2(p1.left, p2.left) && isTree1HasTree2(p1.right, p2.right);
}
树的问题往往比链表复杂，因为指针更多，导致数据结构更复杂。
树问题的算法往往是递归，可是怎么递归呢？先判断A树本身是否包含B树，如果不能再分别判断左右子树是否包含B树，这样又回到了原来的问题。
这道题其实比较绕，就是大问题里套着小问题，先要把小问题想清楚。这个小问题就是大问题的弱化版本：指定A树的某节点，以此节点为根的树（并非其子树）是否包含B节点，写成代码就是boolean isTree1HasTree2(Node p1, Node p2)。
思考的过程可能会复杂迂回，但写出代码来则比较简洁。需要注意递归算法的一个难点是边界的处理，往往会涉及空指针，这道题的方法值得学习。
二叉树最基本的算法是遍历节点，包括先序遍历，中序遍历，后续遍历。虽然看似简单，但却是很多题目的基础（上题使用了先序遍历）。
对于基础知识，要不厌其烦，因为：绝世武功固然好，扎好马步更重要。屠龙之技也源自基本功。所以还是要再写一遍：）
void preOrder(Node p) {
if (p != null) {
visit(p.value);
preOrder(p.left);
preOrder(p.right);
}
}
void inOrder(Node p) {
if (p != null) {
inOrder(p.left);
visit(p.value);
inOrder(p.right);
}
}
void postOrder(Node p) {
if (p != null) {
postOrder(p.left);
postOrder(p.right);
visit(p.value);
}
}
PS：发现自己已经有20+天没写文章了，这段时间事多，心态起伏，没有调整好，时间利用率低。作为一个技术人，要知道到哪里去汲取力量。
