电商网站开发ppt,WordPress主题中文主题,建设通app官方下载,做外贸网站维护费是多少给定一个二叉树#xff0c;检查它是否是镜像对称的。 例如#xff0c;二叉树 [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,2,3,4,4,3] 是对称的。 1/ \2 2/ \ / \
3 4 4 3但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的: 1/ \2 2\ \3 3说明: 如果你可以运用递归和迭代两种方法解决这个问题会很加分。 算法萌新轻拍求指点 XD 此题思路参考了官方题解。 由于是很久没有接触这种类型的题目了所以第一次拿到有点懵。还是看了题解才找回感觉。看这个二叉树是不是对称的主要是看二叉树左边和右边的节点是不是各自相反。每一层都是左右颠倒。所以通过递归判断左树和右树相反的节点的值是不是相同。如果两边都为空正常退出说明递归到树的底部了。如果有一边空了另外一半没空说明有一边的节点没了另外一半还在肯定不是对称的树如果两边对称继续递归节点的左右节点直到递归完全或者发现不对称。代码如下递归 1 class Solution {2 public boolean isSymmetric(TreeNode root) {3 return isMirror(root, root);4 }5 6 boolean isMirror(TreeNode t1, TreeNode t2) 7 {8 if (t1 null t2 null)9 return true;
10 if(t1 null ||t2null)
11 return false;
12 if(t1.valt2.val)
13 {
14 return true isMirror(t1.right, t2.left) isMirror(t1.left, t2.right);
15 }
16 return false;
17 }
18
19 } 第二种方法是迭代虽然知道做法和用意但是在使用上不够熟练。大概思路就是把待处理的节点入队然后依次出队处理获取新的待处理节点入队。在处理时出现了一个问题在迭代时遇到两个都为空的节点不能直接退出循环虽然可能是二叉树的底部但是因为这时队列里可能还有其他未处理的节点等待处理不能直接返回。代码如下迭代 1 class Solution {2 3 4 public boolean isSymmetric(TreeNode root)5 {6 QueueTreeNode queuenew LinkedListTreeNode();7 queue.add(root);8 queue.add(root);9 while(!queue.isEmpty())
10 {
11 TreeNode t1queue.poll();
12 TreeNode t2queue.poll();
13 if(t1null t2null)
14 continue;
15 if(t1null || t2null)
16 {
17 return false;
18 }
19 if(t1.val!t2.val)
20 return false;
21 queue.add(t1.left);
22 queue.add(t2.right);
23 queue.add(t1.right);
24 queue.add(t2.left);
25
26 }
27 return true;
28 }
29 } 转载于:https://www.cnblogs.com/axiangcoding/p/9879329.html
