039对称二叉树

对称二叉树题目链接https://leetcode.cn/problems/symmetric-tree/description/?envTypestudy-plan-v2envIdtop-100-liked我的解答//方法一递归 //时间复杂度O(n) //空间复杂度O(n) public boolean isSymmetric(TreeNode root) { return isEqual(root.left,root.right); } public boolean isEqual(TreeNode left, TreeNode right){ if(leftnullrightnull){ return true; } if(leftnull||rightnull){ return false; } if(!isEqual(left.left,right.right) || !isEqual(left.right,right.left)){ return false; } return left.valright.val; } //方法二迭代采用双端队列 //时间复杂度O(n) //空间复杂度O(n) public boolean isSymmetric(TreeNode root) { if(root.leftnullroot.rightnull){ return true; } if(root.leftnull||root.rightnull){ return false; } DequeTreeNode queue new LinkedList(); queue.addFirst(root.left); queue.addLast(root.right); while(!queue.isEmpty()){ TreeNode left queue.getFirst(); queue.removeFirst(); TreeNode right queue.getLast(); queue.removeLast(); if(left.val!right.val){ return false; } if(left.left!nullright.right!null){ queue.addFirst(left.left); queue.addLast(right.right); } if((left.leftnullright.right!null) || (left.left!nullright.rightnull)){ return false; } if(left.right!nullright.left!null){ queue.addFirst(left.right); queue.addLast(right.left); } if((left.rightnullright.left!null) || (left.right!nullright.leftnull)){ return false; } } return true; }分析​ 方法一解题思路采用递归。递归判断两个对称位置上的节点的值和子树是否也呈对称关系。​ 方法二解题思路采用迭代。通过将位置上对称的两个节点分别从队列的头和尾加入队列每次分别从队列头和尾取出一个节点并删除判断这两个节点的是否相等若不相等则二叉树不对称若相等且两个节点位置上对称的子节点都不为空则按照位置对称关系分别从队列头、尾加入队列若两个节点位置上对称的子节点存在一方为空但另一方不为空的情况就返回false不断重复以上过程若直到队列为空都还未出现不对称的情况则返回true。看了官方题解后的解答//官方题解的方法一与我的解答的方法一思路一致 //方法一递归 //时间复杂度O(n) //空间复杂度O(n) public boolean isSymmetric(TreeNode root) { return check(root.left, root.right); } public boolean check(TreeNode p, TreeNode q) { if (p null q null) { return true; } if (p null || q null) { return false; } return p.val q.val check(p.left, q.right) check(p.right, q.left); } //方法二迭代采用队列 //时间复杂度O(n) //空间复杂度O(n) public boolean isSymmetric(TreeNode root) { //将root加入队列两次可以避免单独讨论边界情况二叉树根节点 return check(root,root); } public boolean check(TreeNode u, TreeNode v){ //队列中连续的两个节点位置上是对称的 QueueTreeNode queue new LinkedList(); queue.offer(u); queue.offer(v); while(!queue.isEmpty()){ u queue.poll(); v queue.poll(); if(unullvnull){ continue; } if((unull || vnull) || u.val!v.val){ return false; } queue.offer(u.left); queue.offer(v.right); queue.offer(u.right); queue.offer(v.left); } return true; }分析方法二采用队列。首先将二叉树的根节点加入队列两次这样可以避免单独讨论边界情况。用两个指针u、v同时移动当u向左孩子移动时v向右孩子移动当u向右孩子移动时v向左孩子移动这样队列中连续的两个节点在位置上总是对称的。另外LinkedList实现的队列是允许插入null的所以在将对称位置的一对节点加入队列时可以避免单独讨论节点为null的情况。总结本题可采用递归和迭代两种方法进行解答。引入队列是把递归程序改写成迭代程序的常用方法。