浅谈电子商务网站建设与管理,google代理服务器地址,徐州专业网站seo,网站建设课程教学改革【递归】【后续遍历】Leetcode 101 对称二叉树 解法一#xff1a; 递归#xff1a;后序遍历 左右中解法二#xff1a; 迭代法#xff0c;用了单端队列 ---------------#x1f388;#x1f388;对称二叉树 题目链接#x1f388;#x1f388;------------------- 解法一… 【递归】【后续遍历】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 rightnull){return true;}if(left ! null rightnull){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) {// 采用迭代法:用了单端队列QueueTreeNode 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;}
}
