[leetcode] Symmetric Tree

发布时间：2020-12-14 03:22:33 所属栏目：大数据来源：网络整理

导读：Given a binary tree,check whether it is a mirror of itself (ie,symmetric around its center). For example,this binary tree? [1,2,3,4,3] ?is symmetric: 1 / 2 2 / / 3 4 4 3 ? But the following? [1,null,3] ?is not: 1 / 2 2 3 3 ? ? 分析：

Given a binary tree,check whether it is a mirror of itself (ie,symmetric around its center).

For example,this binary tree?[1,2,3,4,3]?is symmetric:

    1
   /   2   2
 /  / 3  4 4  3

But the following?[1,null,3]?is not:

    1
   /   2   2
         3    3

分析：这个题目是要判断一棵树是不是中心对称的，要注意这里树时中心对称的，那么就是叶子节点要对称，中间节点值要相等。很容易想到又两个思路，分别是BFS和DFS，最近一直在学习DFS，于是就先用DFS来做这个题目。

方法1：DFS。针对这个题目，首先想到的就是用两个相同的树来作为输入，一棵树无法判断自身是否是中心对称。用深度搜索来解题时，一定要想明白递归终止的条件，在这个题目中，终止条件就是两个节点的值不同，还要注意一点就是如果一个节点为空而另一个节点不为空，也判断为false。代码如下：

 1 class Solution {
 2      public boolean isSymmetric(TreeNode root) {
 3         return helper(root,root);
 4     }
 5 
 6     private boolean helper(TreeNode root1,TreeNode root2) {
 7         if ( root1 == null && root2 == null ) return true;
 8         if ( root1 == null || root2 == null ) return false;
 9         if ( root1.val != root2.val ) return false;
10         
11         return helper(root1.left,root2.right) && helper(root1.right,root2.left);
12     }
13 }

要注意这里最后的return语句是与的关系。

方法2：BFS。这个题目刚开始我想的就是BFS解法，一层一层去观察是否满足题目要求。一般我经常用Queue来实现BFS，代码如下：

 1 class Solution {
 2      public boolean isSymmetric(TreeNode root) {
 3        //BFS解法
 4         if ( root == null ) return true;
 5         Queue<TreeNode> queue = new LinkedList<>();
 6         queue.offer(root);
 7         while ( queue.size() > 0 ){
 8             List<Integer> list = new ArrayList<>();
 9             int size = queue.size();
10             for ( int i = 0 ; i < size ; i ++ ){
11                 TreeNode t = queue.poll();
12                 if ( t.left != null ) {
13                     list.add(t.left.val);
14                     queue.offer(t.left);
15                 }else {
16                     list.add(-1);
17                 }
18                 if ( t.right != null ) {
19                     list.add(t.right.val);
20                     queue.offer(t.right);
21                 }else {
22                     list.add(-1);
23                 }
24             }
25             int low = 0 ;
26             int high = list.size()-1;
27             while (low < high){
28                 if (!list.get(low++).equals(list.get(high--))) return false;
29             }
30         }
31         return true;
32     }
33 }

注意这里15-16行代码表示如果左孩子为空的话，就补上-1，如果不加的话无法判断是否是中心对称。BFS代码感觉应该还有很多地方可以简化，暂时也没去想。

DFS运行时间16ms，BFS运行时间18ms。差距也不是太大。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!