找到二叉树中符合搜索二叉树条件的最大拓扑结构－Java：解法一

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请轻击http://www.captainbed.net

package live.every.day.ProgrammingDesign.CodingInterviewGuide.BinaryTree;
 
import live.every.day.ProgrammingDesign.CodingInterviewGuide.BinaryTree.BinaryTreePrinterSolution2.Node;
 
/**
 * 找到二叉树中符合搜索二叉树条件的最大拓扑结构
 *
 * 【题目】
 * 给定一棵二叉树的根节点root，已知其中所有节点的值都不一样，返回其中最大的且符合搜索二叉树条件的最大拓扑结构的大小。
 *
 * 【难度】
 * 困难
 *
 * 【解答】
 * 方法一：二叉树的节点数为N，时间复杂度为O(N^2)的方法。
 * 首先来看这样一个问题，以节点h为头的树中，在拓扑结构中也必须以h为头的情况下，怎么找到符合搜索二叉树条件的最大结构？这个问题
 * 有一种比较容易理解的解法，我们先考查h的孩子节点，根据孩子节点的值从h开始按照二叉搜索的方式移动，如果最后能移动到同一个孩子
 * 节点上，说明这个孩子节点可以作为这个拓扑的一部分，并继续考查这个孩子节点的孩子节点，一直延伸下去。
 * 也就是说，我们根据一个节点的值，根据这个值的大小，从h开始，每次向左或者向右移动，如果最后能移动到原来的节点上，说明该节点可
 * 以作为以h为头的拓扑的一部分。
 * 解决了以节点h为头的树中，在拓扑结构也必须以h为头的情况下，怎么找到符合搜索二叉树条件的最大结构？接下来只要遍历所有的二叉树
 * 节点，并在以每个节点为头的子树中都求一遍其中的最大拓扑结构，其中最大的那个就是我们想找的结构，它的大小就是我们的返回值。
 * 具体过程请参看如下代码中的getMaxTopologyBSTSize方法。
 * 对于方法一的时间复杂度分析，我们把所有的子树（N个）都找了一次最大拓扑，每找一次所考查的节点数都可能是O(N)个节点，所以方法
 * 一的时间复杂度为O(N^2)。
 *
 * @author Created by LiveEveryDay
 */
 
public class FindMaxTopologyBSTSizeSolution1 {
 
    public static int getMaxTopologyBSTSize(Node root) {
        if (root == null) {
            return 0;
        }
        int max = maxTopo(root, root);
        max = Math.max(getMaxTopologyBSTSize(root.left), max);
        max = Math.max(getMaxTopologyBSTSize(root.right), max);
        return max;
    }
 
    private static int maxTopo(Node h, Node n) {
        if (h != null && n != null && isBSTNode(h, n, n.data)) {
            return maxTopo(h, n.left) + maxTopo(h, n.right) + 1;
        }
        return 0;
    }
 
    private static boolean isBSTNode(Node h, Node n, int data) {
        if (h == null) {
            return false;
        }
        if (h == n) {
            return true;
        }
        return isBSTNode(h.data > data ? h.left : h.right, n, data);
    }
 
    public static void main(String[] args) {
        Node node1 = new Node(5);
        Node node2 = new Node(2);
        Node node3 = new Node(8);
        Node node4 = new Node(1);
        Node node5 = new Node(3);
        Node node6 = new Node(7);
        Node node7 = new Node(6);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        System.out.println(getMaxTopologyBSTSize(node1));
    }
 
}
 
// ------ Output ------
/*
6
*/