LeetCode 100 及 101题

100. 相同的树

给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1:

输入:       1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

输出: true

示例 2:

输入:      1          1
          /           \
         2             2

        [1,2],     [1,null,2]

输出: false

示例 3:

输入:       1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

输出: false

源码：

 1 /**
 2  * definition for a binary tree node.
 3  * public class treenode {
 4  *     int val;
 5  *     treenode left;
 6  *     treenode right;
 7  *     treenode(int x) { val = x; }
 8  * }
 9  */
10 class solution {
11     public boolean issametree(treenode p, treenode q) {
12         if(p == null && q == null)
13             return true;
14         else if(!(p != null && q != null))
15             return false;
16         else {
17             if(p.val == q.val)
18                 return(issametree(p.left, q.left) && issametree(p.right, q.right));
19             else
20                 return false;
21         }      
22     }
23 }

这道题我的解题思路是通过递归遍历这两个树。当两个树当前的节点对应的值相等时，调用自己的方法判断当前节点的左右两个子树是不是也是相同的树，递归终止的条件就是：如果两个树的当前节点都为空，返回true；一个树为空一个不为空，返回false；当前节点的值不相同，也返回false。

101. 对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

    1
   / \
  2   2
   \   \
   3    3

说明:

如果你可以运用递归和迭代两种方法解决这个问题，会很加分。

这道题一看到，我就联想到了上面一题，我们只要从根节点处分开两个子树，同样用递归的方法判断两个子树是不是“相等”，这里只需要把在调用自身方法时的参数改成 “左等于右”&&”右等于左“ 即可，代码如下：

 1 /**
 2  * definition for a binary tree node.
 3  * public class treenode {
 4  *     int val;
 5  *     treenode left;
 6  *     treenode right;
 7  *     treenode(int x) { val = x; }
 8  * }
 9  */
10 class solution {
11     public boolean issymmetric(treenode root) {
12         if(root == null)
13             return true;
14         else
15             return ismirror(root.left, root.right);
16     }
17     public boolean ismirror(treenode m, treenode n) {
18         if(m == null & n == null)
19             return true;
20         else if(m !=null && n !=null && m.val == n.val)
21             return (ismirror(m.left, n.right) && ismirror(m.right, n.left));
22         else 
23             return false; 
24     }
25 }

执行用时 : 1 ms, 在symmetric tree的java提交中击败了99.59% 的用户 
内存消耗 : 34.8 mb, 在symmetric tree的java提交中击败了85.06% 的用户

按照题目要求，还可以用循环的方法做这道题。我的思路是，设定两个 list，分别代表从根节点分开的左边的树和右边的树，在设定两个 int 类型变量作为 list 的光标（index），将两个子树的头加入 list 中。循环体中：当两个树对应节点处的值相等，则将左边树的左、右子节点依次加入 list1，对应的将右边树的右、左子节点；依次加入 list2，然后两个光标自加；若对应节点都为空，则光标自加，然后 continue 继续下一次循环；若只有一个为空，返回 false；其他情况也返回 false。循环的终止条件是，光标的值不小于 list 的长度了，也就是任意一个 list 的每个元素已经循环完了。若循环结束，最后此方法返回 true。

 1 /**
 2  * definition for a binary tree node.
 3  * public class treenode {
 4  *     int val;
 5  *     treenode left;
 6  *     treenode right;
 7  *     treenode(int x) { val = x; }
 8  * }
 9  */
10 class solution {
11     public boolean issymmetric(treenode root) {
12         if (root == null)
13             return true;
14         list<treenode> l1 = new arraylist<treenode>();
15         list<treenode> l2 = new arraylist<treenode>();
16         l1.add(root.left);
17         l2.add(root.right);
18         int cur1 = 0;
19         int cur2 = 0;
20         while(cur1 < l1.size() && cur2 < l2.size()) {
21             if(l1.get(cur1) == null && l2.get(cur2) == null) {
22                 cur1++;
23                 cur2++;
24                 continue;
25             }
26             else if(l1.get(cur1) == null || l2.get(cur2) == null)
27                 return false;
28             else if(l1.get(cur1).val == l2.get(cur2).val) {
29                 l1.add(l1.get(cur1).left);
30                 l1.add(l1.get(cur1++).right);
31                 l2.add(l2.get(cur2).right);
32                 l2.add(l2.get(cur2++).left);
33             }
34             else
35                 return false;
36         }
37         return true;
38     }
39 }

执行用时 : 3 ms, 在symmetric tree的java提交中击败了64.39% 的用户
内存消耗 : 34.6 mb, 在symmetric tree的java提交中击败了88.39% 的用户