自底向上连续传递的只有 size，代表这个 tree 下面最大的 BST subtree size.
size 的绝对值代表以这个 node 为 tree root 的最大 BST subtree 大小；
size 的符号代表到底是不是 BST.
当我们有一个一定非负的变量时(在这里是 size)，符号就成了 boolean 一样的可利用信息。
时间复杂度 O(n)，每个 node 只访问一次，没有重复递归调用。
public class Solution {
private class SubtreeTuple{
// size of tree, negative value to reprensent invalid BST
int size;
// subtree min / max value
int min;
int max;
public SubtreeTuple(int size, int min, int max){
this.size = size;
this.min = min;
this.max = max;
}
}
public int largestBSTSubtree(TreeNode root) {
return Math.abs(helper(root).size);
}
private SubtreeTuple helper(TreeNode root){
if(root == null) return new SubtreeTuple(0, Integer.MAX_VALUE, Integer.MIN_VALUE);
SubtreeTuple left = helper(root.left);
SubtreeTuple right = helper(root.right);
if(left.size < 0 || root.val <= left.max || right.size < 0 || root.val >= right.min){
return new SubtreeTuple(Math.max(Math.abs(left.size), Math.abs(right.size)) * -1,
Math.min(left.min, root.val), Math.max(right.max, root.val));
} else {
// current left + right + root is a valid BST
return new SubtreeTuple(left.size + right.size + 1,
Math.min(root.val, left.min),
Math.max(root.val, right.max));
}
}
}
对于 subtree 特征以及 flag 的处理上，和上一道题可以用完全一样的套路。
唯一的不同在于，我们要返回的是总数，而不是 max ，所以要左右加一起才行。
public class Solution {
private class Tuple{
// ABS : max count
// Sign: +/- , is/not univalue subtree
//
int count;
Integer val;
public Tuple(int count, Integer val){
this.count = count;
this.val = val;
}
}
public int countUnivalSubtrees(TreeNode root) {
return Math.abs(helper(root).count);
}
private Tuple helper(TreeNode root){
if(root == null) return new Tuple(0, null);
Tuple left = helper(root.left);
Tuple right = helper(root.right);
if(left.count < 0 || right.count < 0 ||
(left.val != null && !left.val.equals(root.val)) ||
(right.val != null && !right.val.equals(root.val))){
return new Tuple((Math.abs(left.count) + Math.abs(right.count)) * -1, 0);
} else {
return new Tuple(left.count + right.count + 1, root.val);
}
}
}
如果一个 Tree 是 complete tree，那所有的 subtree 也都是 complete tree.
直接扫肯定 TLE .. 要利用好 complete tree 的定义和性质。
参考了一下论坛之后，写了这个解居然也 TLE，都 O(log n * log n) 了
public class Solution {
public int countNodes(TreeNode root) {
if(root == null) return 0;
if(root.left == null && root.right == null) return 1;
int leftPath = 0;
int rightPath = 0;
TreeNode cur = root;
while(cur != null){
leftPath ++;
cur = cur.left;
}
cur = root;
while(cur != null){
rightPath ++;
cur = cur.right;
}
if(leftPath == rightPath) return (2 << (leftPath - 1)) - 1;
return countNodes(root.left) + countNodes(root.right) + 1;
}
}
能 AC 的代码是论坛上的这个:
如果一个 Tree 是 complete tree，那所有的 subtree 也都是 complete tree.
public class Solution {
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
int l = leftHeight(root.left);
int r = leftHeight(root.right);
if (l == r) { // left side is full
return countNodes(root.right) + (1<<l);
}
return countNodes(root.left) + (1<<r);
}
private int leftHeight(TreeNode node) {
int h = 0;
while (node != null) {
h++;
node = node.left;
}
return h;
}
}
(G) 面经
Given a binary tree, find if there are two subtrees that are the same. (i.e. the tree structures are the same; the values on all corresponding nodes are the same). You should find the largest subtree and don’t use brute force.
