LeetCode(力扣)：对称二叉树

方法一（递归法）：

/** * 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) { //数为空，则对称 if(root == null){ return true; } //交给递归函数 return check(root.left,root.right); } private boolean check(TreeNode leftNode,TreeNode rightNode){ if(leftNode == null && rightNode == null){ return true; } //一边空另一边不空，不对称 if(leftNode == null || rightNode == null){ return false; } //数值不等，不对称 if(leftNode.val != rightNode.val){ return false; } //下一层的比较 boolean outside = check(leftNode.left,rightNode.right); boolean inside = check(leftNode.right,rightNode.left); return outside && inside ; } }

方法二（迭代法）：

/** * 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) { //根节点的判断 if(root == null){ return true; } //初始化队列 Queue<TreeNode> queue = new LinkedList<>(); //将左右节点入队 queue.offer(root.left); queue.offer(root.right); //只要队列不空就循环 while(!queue.isEmpty()){ //同时出列两个节点 TreeNode leftNode = queue.poll(); TreeNode rightNode = queue.poll(); //对刚出来的两个节点进行三层的比较 if(leftNode == null && rightNode == null){ continue; } if(leftNode == null || rightNode == null){ return false; } if(leftNode.val != rightNode.val){ return false; } //对刚才两个节点的下一层节点入队 queue.offer(leftNode.left); queue.offer(rightNode.right); queue.offer(leftNode.right); queue.offer(rightNode.left); } return true; } }

offer():将元素入队

poll()：将元素出队

ArrayList与LinkedList：

ArrayList是数组，LinkedList是链表，这里不能用ArrayList，因为队列对开头元素做处理，开头元素如果出队后续的数组元素要往前移一位时间复杂度为O(n)；而LinkedList只需要将第一个元素和第二个元素断链即可O(1)的时间复杂度。另外ArrayList根本也没有实现Queue接口。

关注我带你每天刷题！！！