树的子结构

本题是《剑指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+天没写文章了，这段时间事多，心态起伏，没有调整好，时间利用率低。作为一个技术人，要知道到哪里去汲取力量。