找到二叉树中的最大搜索二叉子树

递归
技巧的写法
完整测试代码

题目

在这里插入图片描述

递归

解析:
这种题目的解题过程分为三步:

列出所有可能性；
**列出结点需要的信息，并整合信息(成一个结构体)**；
改递归，先假设左和右都给我信息(黑盒)，然后怎么利用左边和右边的信息组出来我该返回的信息，最后basecase(边界)填什么；

具体到这个题目：
第一步，列出所有可能性：

第一种可能性，以node为头的结点的最大二叉搜索子树可能来自它左子树；
第二种可能性，以node为头的结点的最大二叉搜索子树可能来自它右子树；
第三种可能性，左树整体是搜索二叉树，右树整体也是搜索二叉树，而且左树的头是node.left，右树的头是node.right，且左树的最大值< node.value，右树的最小值 > node.value， 那么以我为头的整棵树都是搜索二叉树；

第二步，列出结点需要的信息:

信息一: 左树最大搜索二叉树大小；
信息二: 右树最大搜索二叉树大小；
信息三: 左树上最大搜索二叉树的头部是什么；
信息四: 右树上最大搜索二叉树的头部是什么；
信息五: 左树上的最大值；
信息六: 右树上的最小值；

整合成一个Pair结构: 信息一和信息二整合：size ，信息三和信息四整合 : head(结点类型)，以及信息五和信息六；


`1 2 3 4 5 6 7`	`//返回的类型 static class Pair { public int size; //左右子树的大小 public Node root; //左右子树的头 public int min; public int max; }`

然后第三部就是改成递归，具体如下(是后序遍历的顺序(需要左右的信息来构造头部的信息)):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 static class Node { public int value; public Node left; public Node right; public Node(int value) { this.value = value; } } //返回的类型 static class Pair { public int size; //左右子树的大小 public Node root; //左右子树的头 public int min; public int max; public Pair(int size, Node root, int min, int max) { this.size = size; this.root = root; this.min = min; this.max = max; } } static Node biggestSubBST(Node head) { return rec(head).root; } static Pair rec(Node head) { if (head == null) return new Pair(0, null, Integer.MAX_VALUE, Integer.MIN_VALUE); Pair L = rec(head.left); Pair R = rec(head.right); int msize = (L.root == head.left && R.root == head.right && L.max < head.value && R.min > head.value) ? L.size + R.size + 1 : 0; int maxSize = Math.max(Math.max(L.size, R.size), msize); Node mroot = L.size > R.size ? L.root : R.root; if (maxSize == msize) mroot = head; return new Pair(maxSize, mroot, Math.min(head.value, Math.min(L.min, R.min)), Math.max(head.value, Math.max(L.max, R.max))); }


`1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43`	static class Node { public int value; public Node left; public Node right; public Node(int value) { this.value = value; } } //返回的类型 static class Pair { public int size; //左右子树的大小 public Node root; //左右子树的头 public int min; public int max; public Pair(int size, Node root, int min, int max) { this.size = size; this.root = root; this.min = min; this.max = max; } } static Node biggestSubBST(Node head) { return rec(head).root; } static Pair rec(Node head) { if (head == null) return new Pair(0, null, Integer.MAX_VALUE, Integer.MIN_VALUE); Pair L = rec(head.left); Pair R = rec(head.right); int msize = (L.root == head.left && R.root == head.right && L.max < head.value && R.min > head.value) ? L.size + R.size + 1 : 0; int maxSize = Math.max(Math.max(L.size, R.size), msize); Node mroot = L.size > R.size ? L.root : R.root; if (maxSize == msize) mroot = head; return new Pair(maxSize, mroot, Math.min(head.value, Math.min(L.min, R.min)), Math.max(head.value, Math.max(L.max, R.max))); }

改造的写法

技巧的写法(使用一个数组来记录size,min,max):

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 static Node biggestSubBST2(Node head) { int[] rec = new int[3]; //0 记录size 1记录min 2记录max return rec2(head, rec); } static Node rec2(Node head, int[] rec) { if (head == null) { rec[0] = 0; rec[1] = Integer.MAX_VALUE; rec[2] = Integer.MIN_VALUE; return null; } Node L = rec2(head.left, rec); int lsize = rec[0], lmin = rec[1], lmax = rec[2]; Node R = rec2(head.right, rec); int rsize = rec[0], rmin = rec[1], rmax = rec[2]; int msize = (L == head.left && R == head.right && lmax < head.value && rmin > head.value) ? lsize + rsize + 1 : 0; int maxSize = Math.max(msize, Math.max(lsize, rsize)); Node root = lsize > rsize ? L : R; if (msize == maxSize) root = head; rec[0] = maxSize; rec[1] = Math.min(head.value, Math.min(lmin, rmin)); rec[2] = Math.max(head.value, Math.max(lmax, rmax)); return root; }


`1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25`	static Node biggestSubBST2(Node head) { int[] rec = new int[3]; //0 记录size 1记录min 2记录max return rec2(head, rec); } static Node rec2(Node head, int[] rec) { if (head == null) { rec[0] = 0; rec[1] = Integer.MAX_VALUE; rec[2] = Integer.MIN_VALUE; return null; } Node L = rec2(head.left, rec); int lsize = rec[0], lmin = rec[1], lmax = rec[2]; Node R = rec2(head.right, rec); int rsize = rec[0], rmin = rec[1], rmax = rec[2]; int msize = (L == head.left && R == head.right && lmax < head.value && rmin > head.value) ? lsize + rsize + 1 : 0; int maxSize = Math.max(msize, Math.max(lsize, rsize)); Node root = lsize > rsize ? L : R; if (msize == maxSize) root = head; rec[0] = maxSize; rec[1] = Math.min(head.value, Math.min(lmin, rmin)); rec[2] = Math.max(head.value, Math.max(lmax, rmax)); return root; }

完整测试代码(测试样例)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 ``` /** * 返回一棵树中最大的二叉搜索子树的大小 */ public class BiggestSubBST { static class Node { public int value; public Node left; public Node right; public Node(int value) { this.value = value; } } //返回的类型 static class Pair { public int size; //左右子树的大小 public Node root; //左右子树的头 public int min; public int max; public Pair(int size, Node root, int min, int max) { this.size = size; this.root = root; this.min = min; this.max = max; } } static Node biggestSubBST(Node head) { return rec(head).root; } static Pair rec(Node head) { if (head == null) return new Pair(0, null, Integer.MAX_VALUE, Integer.MIN_VALUE); Pair L = rec(head.left); Pair R = rec(head.right); int msize = (L.root == head.left && R.root == head.right && L.max < head.value && R.min > head.value) ? L.size + R.size + 1 : 0; int maxSize = Math.max(Math.max(L.size, R.size), msize); Node mroot = L.size > R.size ? L.root : R.root; if (maxSize == msize) mroot = head; return new Pair(maxSize, mroot, Math.min(head.value, Math.min(L.min, R.min)), Math.max(head.value, Math.max(L.max, R.max))); } static Node biggestSubBST2(Node head) { int[] rec = new int[3]; //0 记录size 1记录min 2记录max return rec2(head, rec); } static Node rec2(Node head, int[] rec) { if (head == null) { rec[0] = 0; rec[1] = Integer.MAX_VALUE; rec[2] = Integer.MIN_VALUE; return null; } Node L = rec2(head.left, rec); int lsize = rec[0], lmin = rec[1], lmax = rec[2]; Node R = rec2(head.right, rec); int rsize = rec[0], rmin = rec[1], rmax = rec[2]; int msize = (L == head.left && R == head.right && lmax < head.value && rmin > head.value) ? lsize + rsize + 1 : 0; int maxSize = Math.max(msize, Math.max(lsize, rsize)); Node root = lsize > rsize ? L : R; if (msize == maxSize) root = head; rec[0] = maxSize; rec[1] = Math.min(head.value, Math.min(lmin, rmin)); rec[2] = Math.max(head.value, Math.max(lmax, rmax)); return root; } //建立二叉树 static Node build(int[] arr, int index) { if (index >= arr.length


`1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122`	``` /** * 返回一棵树中最大的二叉搜索子树的大小 */ public class BiggestSubBST { static class Node { public int value; public Node left; public Node right; public Node(int value) { this.value = value; } } //返回的类型 static class Pair { public int size; //左右子树的大小 public Node root; //左右子树的头 public int min; public int max; public Pair(int size, Node root, int min, int max) { this.size = size; this.root = root; this.min = min; this.max = max; } } static Node biggestSubBST(Node head) { return rec(head).root; } static Pair rec(Node head) { if (head == null) return new Pair(0, null, Integer.MAX_VALUE, Integer.MIN_VALUE); Pair L = rec(head.left); Pair R = rec(head.right); int msize = (L.root == head.left && R.root == head.right && L.max < head.value && R.min > head.value) ? L.size + R.size + 1 : 0; int maxSize = Math.max(Math.max(L.size, R.size), msize); Node mroot = L.size > R.size ? L.root : R.root; if (maxSize == msize) mroot = head; return new Pair(maxSize, mroot, Math.min(head.value, Math.min(L.min, R.min)), Math.max(head.value, Math.max(L.max, R.max))); } static Node biggestSubBST2(Node head) { int[] rec = new int[3]; //0 记录size 1记录min 2记录max return rec2(head, rec); } static Node rec2(Node head, int[] rec) { if (head == null) { rec[0] = 0; rec[1] = Integer.MAX_VALUE; rec[2] = Integer.MIN_VALUE; return null; } Node L = rec2(head.left, rec); int lsize = rec[0], lmin = rec[1], lmax = rec[2]; Node R = rec2(head.right, rec); int rsize = rec[0], rmin = rec[1], rmax = rec[2]; int msize = (L == head.left && R == head.right && lmax < head.value && rmin > head.value) ? lsize + rsize + 1 : 0; int maxSize = Math.max(msize, Math.max(lsize, rsize)); Node root = lsize > rsize ? L : R; if (msize == maxSize) root = head; rec[0] = maxSize; rec[1] = Math.min(head.value, Math.min(lmin, rmin)); rec[2] = Math.max(head.value, Math.max(lmax, rmax)); return root; } //建立二叉树 static Node build(int[] arr, int index) { if (index >= arr.length

二叉树打印见这个博客
测试效果:
这里写图片描述