872. Leaf-Similar Trees

Consider all the leaves of a binary tree. From left to right order, the values of those leaves form a leaf value sequence.

For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8).

Two binary trees are considered leaf-similar if their leaf value sequence is the same.

Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.

Note:

Both of the given trees will have between 1 and 100 nodes

 1 //Time: O(n), Space: O(logn) 其实是recusive stack的空间  
 2   public boolean leafSimilar(TreeNode root1, TreeNode root2) {
 3         if (root1 == null && root2 == null) {
 4             return true;
 5         }
 6         
 7         if (root1 == null || root2 == null) {
 8             return false;
 9         }
10         
11         StringBuilder s1 = new StringBuilder();//不可以用string因为recusive每次return又变成原来的string，所以string永远是初始值
12         StringBuilder s2 = new StringBuilder();
13         leaf(root1, s1);
14         leaf(root2, s2);
15         return s1.toString().equals(s2.toString());//note:stringbuilder用equal比较是错的，因为stringbuilder没有重写equal这个方法，所以equal本质仍然是==，比较的是地址
16     }
17     
18     private void leaf(TreeNode root, StringBuilder sb) {
19         if (root == null) {
20             return;
21         }
22         
23         if (root.left == null && root.right == null) {
24             sb.append(root.val);
25         }
26         
27         leaf(root.left, sb);
28         leaf(root.right, sb);
29     }