狼雨的网站,微信商城怎么开商城,最新国际要闻,河南工程建设信息网查询题目 101. 对称二叉树 思路 使用层序遍历#xff0c;遍历当前层的节点时#xff0c;如该节点的左#xff08;右#xff09;孩子为空#xff0c;在list中添加null#xff0c;否则加入左#xff08;右#xff09;孩子的值。每遍历完一层则对当前list进行判断#xff0c…题目 101. 对称二叉树 思路 使用层序遍历遍历当前层的节点时如该节点的左右孩子为空在list中添加null否则加入左右孩子的值。每遍历完一层则对当前list进行判断这里判断我用了一个很笨的方法前面记录下一层节点值时就设置了两个list其中一个用来翻转然后判断这两个list是否相等来判断数是否为对称树。 去看了解析有两种方法递归法、使用双端队列进行迭代。 代码
public boolean isSymmetric(TreeNode root) {
// 迭代写法使用双端队列if(root null){return true;}DequeTreeNode deque new LinkedListTreeNode();deque.offerFirst(root.left);deque.offerLast(root.right);while (!deque.isEmpty()){TreeNode temp_left deque.pollFirst();TreeNode temp_right deque.pollLast();if(temp_left null temp_right null){continue;}if(temp_left null || temp_right null || temp_left.val ! temp_right.val){return false;}deque.offerFirst(temp_left.right);deque.offerFirst(temp_left.left);deque.offerLast(temp_right.left);deque.offerLast(temp_right.right);}return true;}public boolean isSymmetric_2(TreeNode root) {
// 递归写法分解为判断每个子树是否对称if(root null){return true;}return comp(root.left, root.right);}public boolean comp(TreeNode left, TreeNode right){if(left null right ! null){return false;}if(left ! null right null) {return false;}if(left null right null){return true;}if(left.val ! right.val){return false;}
// 当左右子树都不为空且值相等时对其左右子树继续进行判断return comp(left.left, right.right)comp(left.right, right.left);}public boolean isSymmetric_1(TreeNode root) {
// 判断二叉树是否为轴对称二叉树
// 直接拿层序遍历的结果看逆转后是否还为原数组来进行判断if(root null){return false;}QueueTreeNode queue new ArrayDequeTreeNode();queue.add(root);while (!queue.isEmpty()){int len queue.size();ListInteger temp_list new ArrayListInteger();ListInteger temp_re new ArrayListInteger();while (len 0){TreeNode temp queue.poll();if(temp.left null){temp_list.add(null);temp_re.add(null);}if(temp.left ! null){queue.add(temp.left);temp_list.add(temp.left.val);temp_re.add(temp.left.val);}if(temp.right null){temp_list.add(null);temp_re.add(null);}if(temp.right ! null){queue.add(temp.right);temp_list.add(temp.right.val);temp_re.add(temp.right.val);}len--;}Collections.reverse(temp_list);if(!temp_list.equals(temp_re)){return false;}}return true;}
