需要检查子树结构的题都需要一个 helper 函数，带着两个 root，递归解决。 如果默认没给，就自己写一个。
子树类问题如果出现不连续，或者需要多个子树信息的时候，自定义 SubtreeTuple 是最合适的选择。
在 size / count 这种非负情况下，还可以把符号当 flag 用;
这种递归结构中先处理完 left / right 再来汇总结果的，其实就是 post-order traversal. 这点在 search 类 dfs 中也很常见，比如安卓解锁，数解锁方式数量的做法。
Tree 类问题另一个递归转迭代的思路就是，观察下递归是 pre-order, in-order 还是 post-order，然后对应的靠 stack 保存状态，模拟整个过程即可。
Trivial problem.
Copy public class Solution {
public boolean isSameTree ( TreeNode p , TreeNode q) {
if (p == q) return true ;
if (p == null || q == null ) return false ;
if ( p . val != q . val ) return false ;
return isSameTree( p . left , q . left ) && isSameTree( p . right , q . right ) ;
}
} 迭代写法，思路很简单，就是按照同一个顺序做 DFS (pre-order)，每步上检查下元素值和 stack 大小就行，如果两个树一样，那么在迭代过程中所有的状态也都应该是一样的。
这个写法的子树访问路线以及顺序，和递归的写法是完全一样的。也就是说，其实这个迭代写法的思路，是完全建立在递归写法的代码上：
Copy public boolean isSameTree( TreeNode p , TreeNode q) {
Stack < TreeNode > stack1 = new Stack <>();
Stack < TreeNode > stack2 = new Stack <>();
if (p != null ) stack1 . push (p);
if (q != null ) stack2 . push (q);
while ( ! stack1 . isEmpty () && ! stack2 . isEmpty ()){
TreeNode node1 = stack1 . pop ();
TreeNode node2 = stack2 . pop ();
// Check cur
if ( node1 . val != node2 . val ) return false ;
// Add Next
if ( node1 . right != null ) stack1 . push ( node1 . right );
if ( node2 . right != null ) stack2 . push ( node2 . right );
if ( stack1 . size () != stack2 . size ()) return false ;
if ( node1 . left != null ) stack1 . push ( node1 . left );
if ( node2 . left != null ) stack2 . push ( node2 . left );
if ( stack1 . size () != stack2 . size ()) return false ;
}
return stack1 . size () == stack2 . size ();
} 这题和上一题非常像，都是给你两个 root，去判断他们的结构，考虑到要做 symmetric tree 所以每次递归的时候参数是 p.left 和 q.right ，而不是每次都同一方向。
Copy public class Solution {
public boolean isSymmetric ( TreeNode root) {
if (root == null ) return true ;
return isSymmetric( root . left , root . right ) ;
}
private boolean isSymmetric ( TreeNode p , TreeNode q){
if (p == q) return true ;
if (p == null || q == null ) return false ;
if ( p . val != q . val ) return false ;
return isSymmetric( p . left , q . right ) && isSymmetric( p . right , q . left ) ;
}
}
这题用迭代的写法和思路，思路像 google onsite 面经里出现过的，交替输出 kth level 的节点。 Queue(deque) 的写法很好写，空间优化上就需要用 push 顺序相反的两个 stack 了。
具体思路参考了下论坛，我当初的写法是用两个 queue 存两个 level，对于每个 level 用类似 two pointer 的方式去检查元素，不过因为 queue 的大小一直变动，而且 queue 的 implementation 直接 access by index 也不太方便，写起来很麻烦。
比较好的思路是根据题意，直接把每个 level 拆成两个 queue，像 segment tree 似的，一个 queue 对应左子树，一个 queue 对应右子树，插入的时候，如果 q1 放左节点，q2 就放右节点，vice versa. 如果结果正确的话，两个 queue 里面的元素完全一样。
Copy public class Solution {
public boolean isSymmetric ( TreeNode root) {
if (root == null ) return true ;
Queue < TreeNode > q1 = new LinkedList < TreeNode >();
Queue < TreeNode > q2 = new LinkedList < TreeNode >();
evalAndAdd(root , root , q1 , q2) ;
while ( ! q1 . isEmpty ()){
int size = q1 . size ();
for ( int i = 0 ; i < size; i ++ ){
TreeNode n1 = q1 . poll ();
TreeNode n2 = q2 . poll ();
if ( ! evalAndAdd( n1 . left , n2 . right , q1 , q2) ) return false ;
if ( ! evalAndAdd( n1 . right , n2 . left , q1 , q2) ) return false ;
}
}
return true ;
}
private boolean evalAndAdd ( TreeNode n1 , TreeNode n2 , Queue < TreeNode > q1 , Queue < TreeNode > q2){
if (n1 == null && n2 == null ) return true ;
if (n1 == null || n2 == null ) return false ;
if ( n1 . val == n2 . val ){
q1 . offer (n1);
q2 . offer (n2);
return true ;
}
return false ;
}
} 同样一题，用 stack 省空间的做法，其实和两个 queue 的思路基本完全一样。。
两种做法都是把树 traverse 了一遍，只不过顺序不同。有的时候我觉得，各种 tree 的 traversal，其实就像花式 for loop 一个 array 一样。
这题的双 stack 代码和 Same Tree 基本一样，只是 push 顺序不同而已。其代码的相似与不同可以追溯到各自的递归解法中，Tree 类问题递归结构是迭代写法的指引。
Copy public boolean isSymmetric( TreeNode root) {
if (root == null ) return true ;
Stack < TreeNode > stack1 = new Stack <>();
Stack < TreeNode > stack2 = new Stack <>();
stack1 . push (root);
stack2 . push (root);
while ( ! stack1 . isEmpty () && ! stack2 . isEmpty ()){
TreeNode node1 = stack1 . pop ();
TreeNode node2 = stack2 . pop ();
if ( node1 . val != node2 . val ) return false ;
if ( node1 . left != null ) stack1 . push ( node1 . left );
if ( node2 . right != null ) stack2 . push ( node2 . right );
if ( stack1 . size () != stack2 . size ()) return false ;
if ( node1 . right != null ) stack1 . push ( node1 . right );
if ( node2 . left != null ) stack2 . push ( node2 . left );
if ( stack1 . size () != stack2 . size ()) return false ;
}
return stack1 . size () == stack2 . size ();
} 这题和 Binary Tree Maximum Path Sum 的联系非常密切，要一起研究。
这题因为执着于用一个 helper 函数同时做 “验证BST” 和 “数子树大小”的工作，做了很多次失败提交。
需要传递的信息太多就自定义 SubtreeTuple
同时这题的定义也稍微有点模糊，正确定义是：如果整棵树都是 BST，那么返回 tree size; 反之返回左右子树的最大 size ，而不考虑 root. 这个 “不考虑root” 稍微有点歧义，因为如果右子树不是 BST，左子树是 BST，并且 root.val 大于左子树的情况下，按理讲算上 root 也是一个 BST 的，只是这题我们不考虑而已。
假如我们只用一个返回 int 的函数来层层递归，需要处理这些问题：
正解的的子树很可能和 root 以及上层的 node 不是连续的;
如果某个子树不是 BST (size = 0)，也意味着上层的所有 node 都不能包含这个子树;
给定 root，要验证这个 root 是否在合理的左右子树极值区间内；
这些问题都不是一个 int 就能完美解决的。
时间复杂度 O(n log n)，一次检查 BST/getSize 为O(n)，最多重复调用 O(log n) 次
Copy public class Solution {
public int largestBSTSubtree ( TreeNode root) {
if (root == null ) return 0 ;
if ( isBST(root , null , null ) ) return getSize(root) ;
return Math . max ( largestBSTSubtree( root . left ) , largestBSTSubtree( root . right ) );
}
private boolean isBST ( TreeNode root , Integer min , Integer max){
if (root == null ) return true ;
if (min != null && root . val <= min) return false ;
if (max != null && root . val >= max) return false ;
return isBST( root . left , min , root . val ) && isBST( root . right , root . val , max) ;
}
private int getSize ( TreeNode root){
if (root == null ) return 0 ;
return getSize( root . left ) + getSize( root . right ) + 1 ;
}
} 自定义 SubtreeTuple 的写法：
自底向上连续传递的只有 size，代表这个 tree 下面最大的 BST subtree size.
size 的绝对值代表以这个 node 为 tree root 的最大 BST subtree 大小；
当我们有一个一定非负的变量时(在这里是 size)，符号就成了 boolean 一样的可利用信息。
时间复杂度 O(n)，每个 node 只访问一次，没有重复递归调用。
Copy 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 ，所以要左右加一起才行。
Copy 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) 了
Copy 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.
1 << l 其实包含了每一层上加一（root） 的步骤。
按照这个代码的执行方式，每一次的左右子树必定有一个是 prefect tree，于是可以根据 depth 决定下一步处理哪棵。
Copy 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) 面经
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=197372&highlight=google
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.
贴个 hx 的思路，仔细讨论和思考之后觉得靠谱。
假设identical的子树share一个group id. NULL的group id是0.其它子树的group id按照group在后序遍历中第一次出现的时间顺序决定。 这样我们可以一边后序遍历子树，一边建两个hashmap:
(root value, group id of left, group id of right) -> group id of root group id -> subtrees of this group
这样我们做一遍后序遍历同时维护层数最高、subtree数量>=2的group id就行了。
这个其实跟用整棵子树的serialization作为key做法差不多，只是对key作了压缩。
如果只是要 size 的话，一个 hashmap 就够。
按着这个思路试着写了一下，附带两个 test case，返回的是最大 subtree 的 size.
第二个是左右完全一样的 binary tree，中间缺一个 leaf node，返回 6.
Copy public class Solution {
private static class TreeNode {
int val;
TreeNode left , right;
public TreeNode ( int val){
this . val = val;
}
}
private static class TreeTuple {
String key;
int id;
int size;
public TreeTuple ( String key , int id , int size){
this . key = key;
this . id = id;
this . size = size;
}
}
public static int largestSubtree ( TreeNode root){
HashMap < String , Integer > keyMap = new HashMap <>();
HashMap < Integer , List < TreeTuple >> groupMap = new HashMap <>();
int [] id = new int [ 1 ];
id[ 0 ] = 1 ;
postOrder(root , keyMap , groupMap , id) ;
Iterator < Integer > iter = groupMap . keySet () . iterator ();
int maxSize = 0 ;
while ( iter . hasNext ()){
int groupId = iter . next ();
List < TreeTuple > list = groupMap . get (groupId);
if ( list . size () > 1 ) maxSize = Math . max (maxSize , list . get ( 0 ) . size );
}
return maxSize;
}
// keyMap : Key - String - (val, leftId, rightId)
// Val - Integer - groupId
// groupMap : Key - Integer - groupId
// Val - Integer - number of occurrances
private static TreeTuple postOrder ( TreeNode root , HashMap < String , Integer > keyMap ,
HashMap < Integer , List < TreeTuple >> groupMap , int [] id){
if (root == null ) return new TreeTuple( "0,0,0" , 0 , 0 ) ;
TreeTuple left = postOrder( root . left , keyMap , groupMap , id) ;
TreeTuple right = postOrder( root . right , keyMap , groupMap , id) ;
int curId;
TreeTuple curTuple;
String key = "" + root . val + "," + left . id + "," + right . id ;
if ( ! keyMap . containsKey (key)){
curId = id[ 0 ] ++ ;
keyMap . put (key , curId);
groupMap . put (curId , new ArrayList <>());
curTuple = new TreeTuple(key , curId , left . size + right . size + 1 ) ;
groupMap . get (curId) . add (curTuple);
} else {
curId = keyMap . get (key);
curTuple = new TreeTuple(key , curId , left . size + right . size + 1 ) ;
groupMap . get (curId) . add (curTuple);
}
return curTuple;
}
public static void main ( String [] args) {
/*
TreeNode root = new TreeNode(5);
TreeNode root2 = new TreeNode(9);
TreeNode root3 = new TreeNode(2);
TreeNode root4 = new TreeNode(7);
TreeNode root5 = new TreeNode(3);
TreeNode root6 = new TreeNode(12);
TreeNode root7 = new TreeNode(10);
TreeNode root8 = new TreeNode(9);
TreeNode root9 = new TreeNode(2);
TreeNode root10 = new TreeNode(7);
TreeNode root11 = new TreeNode(3);
root.left = root2;
root.right = root6;
root2.left = root3;
root2.right = root4;
root4.left = root5;
root6.left = root7;
root6.right = root8;
root8.left = root9;
root8.right = root10;
root10.left = root11;
*/
TreeNode root = new TreeNode( 0 ) ;
TreeNode rootl2 = new TreeNode( 1 ) ;
TreeNode rootr3 = new TreeNode( 1 ) ;
TreeNode rootl4 = new TreeNode( 2 ) ;
TreeNode rootr5 = new TreeNode( 2 ) ;
TreeNode rootl6 = new TreeNode( 3 ) ;
TreeNode rootr7 = new TreeNode( 3 ) ;
TreeNode rootl8 = new TreeNode( 4 ) ;
TreeNode rootr9 = new TreeNode( 4 ) ;
TreeNode rootl10 = new TreeNode( 5 ) ;
TreeNode rootr11 = new TreeNode( 5 ) ;
TreeNode rootl12 = new TreeNode( 6 ) ;
TreeNode rootr13 = new TreeNode( 6 ) ;
root . left = rootl2;
root . right = rootr3;
rootl2 . left = rootl4;
rootl2 . right = rootl6;
rootl4 . left = rootl8;
rootl4 . right = rootl10;
rootl6 . right = rootl12;
rootr3 . left = rootr5;
rootr3 . right = rootr7;
rootr5 . left = rootr9;
rootr5 . right = rootr11;
rootr7 . right = rootr13;
System . out . println ( largestSubtree(root) );
}
} 