SubtreeOfAnotherTreeOPT [source code]

public class SubtreeOfAnotherTreeOPT {
    public boolean isSubtree(TreeNode s, TreeNode t) {
        return isSubtree(s, t, false);
    }

    private boolean isSubtree(TreeNode s, TreeNode t, boolean isCheckingEquality) {
        if (s == null && t == null) return true;
        else if (s == null || t == null) return false;
        else {
            if (s.val == t.val) {
                if (isSubtree(s.left, t.left, true) && isSubtree(s.right, t.right, true)) return true;
            } else if (isCheckingEquality) return false;
            return isSubtree(s.left, t, isCheckingEquality) || isSubtree(s.right, t, isCheckingEquality);
        }        
    }

    public static void main(String[] args) {
        SubtreeOfAnotherTreeOPT tester = new SubtreeOfAnotherTreeOPT();
    }
}

这个是 submission 最优解, 14(99.97); 这个解法总体的逻辑结构和我自己的 ver1非常相似, 但是他加了一个非常强大的优化, 避免了我的double recursion的问题;

这个优化就是单独做了一个 helper, 然后这个 helper 有一个额外的 arg, 这个 arg 就可以避免需要单独判断equality.
这个问题的难点出现在s.val == t.val的情况下.

从 declarative 的角度来理解:
我们前面说过, recursive return value, 我们希望它具有DP Property, 但是如果我们单纯的认为这里的返回值就是"is t a subtree of s", 那么你会发现通过"t.left is subtree of s.left" && "t.right is subtree of s.right"是无法推出"t is subtree of s"的, 也就是这个返回值不具有 DP Property;
为此, 我们用一个新的技术:

additional constraint for DP property

也就是我们让我们的返回值所代表的信息less general, more limited, 但是正因为加了额外的 constraint, 结果反过来这个返回值就具有 DP Property 了;
想了很长时间, 这个问题好像从 declarative 的角度并不好理解;

从 imperative 的角度来理解:
之前学习 recursion 的时候, 我们就学习过一个技巧, use accum to pass upper level information down to lower level. 这里这个算法做的事情其实是类似的.
当我们出现s.val == t.val的时候, 我们想要做的事情其实还是要检查s.left == t.left && s.right == t.right(当然不是直接用 == 来做). 这里 arg3的这个 flag, 就是用来区分我们往下要检查的是 isSubtree 还是 isEqual. 理解了这个问题, 就很容易理解这里的代码的意思了. 比如你可以观察, 对于这个 flag 的操作, 只在当前 level 出现 val 相等的情况下才进行操作. 假如我们有一个极端 case, s 和 t 所以的 val 都不相等, 那么最后这个 flag 在整个过程中就都是被无视的状态.
当这个flag 是 on 的状态的时候, 向下的过程中检查的就是 equality. 这个 equality 的检查也很简单, 检查 tree 的 equality 本身确实也是只要一个 boolean 就可以完成的. 这个有点类似以前写段落检测的算法, 就是一个on flag: 只要当前 level 检查到 val 相等, 那么这个 flag 就保持 on, 否则立刻return false.
严格来说, 这个 flag 叫做switch to check equality其实并不准确, 因为无论这个 flag 是 true 还是 false, 在not checking equality的极端, 它都是被无视的. 在代码写法上的技巧就是, 把那些不无视 flag 的代码写在前面:

如果 val 相等:  
    向下 check equality. 如果上面下来的时候已经是在checking equality, 也无所谓. 我restart 跟 continue 是一个意思.  
否则, val 不相等, 看目前是在check equality.  
    目前是在checking equality状态, 那么return false;  
    否则, do nothing;   
否则, val 不相等(不可能restart checking equality), 同时也不是在checking equality状态, 那么直接向下 check isSubtree.

这个 flag 其实可以叫做一个run flag. 它做到的东西跟一般的 accum 很类似, 就是把the information previously on the path to THIS node都集合起来传递给this node, 只不过这个是一个 boolean, 相对来说简单一些. 如果一定要用 accum 来理解, 假如previously on the path一直是 equal 的, 那么这个 accum 保存的就类似 true && true && ... && true (这里的这个 iterate 的顺序严格来说是一个 DFS).

这个真的是一个集efficiency and elegancy于一身的一个算法;

editorial 给出的一个解:

public class Solution {  
    HashSet < String > trees = new HashSet < > ();  
    public boolean isSubtree(TreeNode s, TreeNode t) {  
        String tree1 = preorder(s, true);  
        String tree2 = preorder(t, true);  
        return tree1.indexOf(tree2) >= 0;  
    }  
    public String preorder(TreeNode t, boolean left) {  
        if (t == null) {  
            if (left)  
                return "lnull";  
            else  
                return "rnull";  
        }  
        return "#"+t.val + " " +preorder(t.left, true)+" " +preorder(t.right, false);  
    }  
}

这个思路还是比较清奇的, 而且也没有 double recursion 的问题, 给出了 tree 问题的另外一个思路: 直接 serialize 之后处理, 毕竟 tree 的 serialize 还是很容易的;
注意这里他用 lnull 和 rnull 这两个来区分左右的分解, 如果用 timestamp 的观点, 其实这两个我个人感觉用左右括号似乎更直观;

不过 editorial 的另外一个解并不怎么样, 用的还是 double recursion.

discussion并没有人给出更好的解;

Problem Description

Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node's descendants. The tree s could also be considered as a subtree of itself.

Example 1:
Given tree s:

 3  
/ \  

4 5
/ \
1 2
Given tree t:
4
/ \
1 2
Return true, because t has the same structure and node values with a subtree of s.
Example 2:
Given tree s:

 3  
/ \  

4 5
/ \
1 2
/
0
Given tree t:
4
/ \
1 2
Return false.
Difficulty:Easy
Category:Algorithms
Acceptance:41.02%
Contributor: xljob
Companies
facebook ebay
Related Topics
tree
Similar Questions
Count Univalue Subtrees Most Frequent Subtree Sum