找到二叉树中符合搜索二叉树条件的最大拓扑结构

找到二叉树中符合搜索二叉树条件的最大拓扑结构

题目：找到二叉树中符合搜索二叉树条件的最大拓扑结构

《程序员代码面试指南》第38题 P124 难度：校★★★☆

本题有两种解法，时间复杂度分别为O(N2)和O(N)。

首先来看方法一，核心思路就是把整个二叉树中每个节点都作为一次头节点，寻找以它为头节点的情况下的最大搜索二叉树拓扑结构。其中最大的那个就是我们想找的结构。

直接来看代码：

public int bstTopoSize1(Node head) {
    if (head == null) {
        return 0;
    }
    int max = maxTopo(head, head);
    max = Math.max(bstTopoSize1(head.left), max);
    max = Math.max(bstTopoSize1(head.right), max);
    return max;
}

public int maxTopo(Node h, Node n) {
    if (h != null && n != null && isBSTNode(h, n, n.value)) {
        return maxTopo(h, n.left) + maxTopo(h, n.right) + 1;
    }
    return 0;
}

public boolean isBSTNode(Node h, Node n, int value) {
    if (h == null) {
        return false;
    }
    if (h == n) {
        return true;
    }
    return isBSTNode(h.value > value ? h.left : h.right, n, value);
}

算法用到了三层递归。

第一层递归如上所述，就是以各个节点为头节点的情况下来对比各种情况下的搜索二叉树最大拓扑结构。并且不断的取最大值，最后返回的值就是整个二叉树中符合条件的最大值。

第二层递归则是在以当前节点为头节点的情况下，寻找最大拓扑结构。如果一个节点不满足条件，则不再往其子节点寻找。反之，则一直沿着子树往下寻找。

第三层递归就是判断当前节点是否可以作为这个拓扑的一部分。即从当前头节点出发，按照二叉搜索的方式移动。能找到当前节点，则返回true。不能则返回false。

三层递归的关系也很好理解。第一层递归需要用到什么？需要用到以各个节点为头节点的情况下的最大拓扑结构的节点数。这就是第二层递归。而第二层递归需要用到什么？需要用到判断每个节点是否可以作为这个拓扑的一部分。这就是第三层递归。而第三层递归就是最内层，从当前头节点开始不断往下递归寻找当前节点，来返回true或者false。

时间复杂度为O(N)的第二种方法待更，比较复杂。