【递归】【后续遍历】【迭代】【队列】Leetcode 101 对称二叉树

---------------🎈🎈对称二叉树 题目链接🎈🎈-------------------

解法一： 递归：后序遍历 左右中

时间复杂度O(N)
空间复杂度O(N)

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isSymmetric(TreeNode root) {// 递归return compare(root.left, root.right);}public boolean compare(TreeNode left, TreeNode right){ // 确定递归的参数和返回值if(left == null && right==null){return true;}if(left != null && right==null){return false;}if(left == null && right!=null){return false;}if(left.val != right.val){return false;}// 递归逻辑：继续比较左右两个子树的内外侧【相当于后序遍历，最后返回内侧和外侧的比较结果】boolean compareOutside = compare(left.left, right.right); boolean compareInside = compare(left.right, right.left);return compareInside && compareOutside;  // 内外侧都是true的时候就返回true}}       

解法二： 迭代法，用了单端队列

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public boolean isSymmetric(TreeNode root) {// 采用迭代法:用了单端队列Queue<TreeNode> myqueue = new LinkedList<>();myqueue.add(root.left);myqueue.add(root.right);while(!myqueue.isEmpty()){TreeNode leftnode = myqueue.poll();TreeNode rightnode = myqueue.poll();if(leftnode == null && rightnode == null){continue;}if(leftnode != null && rightnode == null){return false;}if(leftnode == null && rightnode != null){return false;}if(leftnode.val != rightnode.val){return false;}myqueue.add(leftnode.left);myqueue.add(rightnode.right);myqueue.add(leftnode.right);myqueue.add(rightnode.left);}return true;}
}