题目
二叉树的拓扑结构概念：任何经过left和right指针，连成一片的节点，都叫一个拓扑结构。只要可以连在一起，都叫拓扑结构，区别与前一题的最大而二叉搜索子树。
给定一棵二叉树的头节点head，请返回满足二叉搜索树条件的最大拓扑结构的大小。
分析
- 首先计算出以包含根节点的最大二叉搜索树的大小，实现方法可以遍历树中的各个节点，然后看根节点按照二叉搜索树的顺序是否可以走到这里来，如果可以，那么当前节点在二叉树结构中
- 然后计算出左子树包含的最大拓扑结构以及右子树的最大拓扑结构，比较出最大的值，返回即可。
代码
// 定义Node节点
public static class Node{
public int value;
public Node left;
public Node right;
public Node(int data) {
this.value=data;
}
}
//***************************************解法一********************************************************
// 定义主函数入口
public static int getMaxSize(Node root) {
// 如果当前的root为null，直接返回0
if(root == null) return 0;
// 计算以当前root为根节点的最大拓扑二叉搜索树的大小
int max = maxTuoSize(root,root);
// 递归进入计算左子树的过程，与原始的max进行比较
max = Math.max(max,getMaxSize(root.left));
// 递归进入计算右子树的过程，与更新的max进行比较
max = Math.max(max,getMaxSize(root.right));
// 返回结果
return max;
}
// 获取以root为根节点的最大拓扑结构（该拓扑树一定包含root节点）
private static int maxTuoSize(Node root, Node cur) {
// 如果当前的cur在以root为根节点的搜索二叉树中
if(cur != null && isBSTNode(root,cur)) {
// 左边的结果加中间的结果再加1
return maxTuoSize(root,cur.left) + maxTuoSize(root,cur.right) + 1;
}
return 0;
}
// 检查cur节点是否存在于以root为根节点的搜索二叉树中
private static boolean isBSTNode(Node root, Node cur) {
if(root == null) {
return false;
}
if(cur == root) {
return true;
}
return isBSTNode(root.value > cur.value ? root.left : root.right, cur);
}
//######################以下为测试集#############################
// for test -- print tree
public static void printTree(Node head) {
System.out.println("Binary Tree:");
printInOrder(head, 0, "H", 17);
System.out.println();
}
public static void printInOrder(Node head, int height, String to, int len) {
if (head == null) {
return;
}
printInOrder(head.right, height + 1, "v", len);
String val = to + head.value + to;
int lenM = val.length();
int lenL = (len - lenM) / 2;
int lenR = len - lenM - lenL;
val = getSpace(lenL) + val + getSpace(lenR);
System.out.println(getSpace(height * len) + val);
printInOrder(head.left, height + 1, "^", len);
}
public static String getSpace(int num) {
String space = " ";
StringBuffer buf = new StringBuffer("");
for (int i = 0; i < num; i++) {
buf.append(space);
}
return buf.toString();
}
public static void main(String []args) {
//System.out.println("Hello");
Node node=new Node(12);
node.left=new Node(10);
node.right=new Node(13);
node.left.left=new Node(4);
node.left.right=new Node(14);
node.right.left=new Node(20);
node.right.right=new Node(16);
node.left.left.left=new Node(2);
node.left.left.right=new Node(5);
node.left.right.left=new Node(11);
node.left.right.right=new Node(15);
printTree(node);
System.out.println(getMaxSize(node));
//System.out.println(getMaxSize2(node));
}
网友评论