当前位置 博文首页 > Yawn：Leetcode——对称二叉树 / 平衡二叉树
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
思路简单：
/**
* 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 help(root.left, root.right);
}
public boolean help(TreeNode left, TreeNode right){
if(left == null && right == null)
return true;
if(left == null || right == null || left.val != right.val)
return false;
return help(left.left, right.right) && help(left.right, right.left);
}
}
原理其实一样，注意：
/**
* 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> queue = new LinkedList<>();
if (root == null)
return true;
//左子节点和右子节点同时入队
queue.add(root.left);
queue.add(root.right);
//如果队列不为空就继续循环
while (!queue.isEmpty()) {
//每次两个出队
TreeNode left = queue.poll(), right = queue.poll();
//如果都为空继续循环，考虑另外节点的左右节点可能对称
if (left == null && right == null)
continue;
//如果一个为空一个不为空，说明不是对称的，直接返回false
if (left == null ^ right == null)
return false;
//如果这两个值不相同，也不是对称的，直接返回false
if (left.val != right.val)
return false;
//这里要记住入队的顺序，他会每两个两个的出队。
//左子节点的左子节点和右子节点的右子节点同时
//入队，因为他俩会同时比较。
//左子节点的右子节点和右子节点的左子节点同时入队，
//因为他俩会同时比较
queue.add(left.left);
queue.add(right.right);
queue.add(left.right);
queue.add(right.left);
}
return true;
}
}
class Solution {
public boolean isBalanced(TreeNode root) {
if (root == null) return true;
return Math.abs(depth(root.left) - depth(root.right)) <= 1
&& isBalanced(root.left)
&& isBalanced(root.right);
}
private int depth(TreeNode root) {
if (root == null) return 0;
return Math.max(depth(root.left), depth(root.right)) + 1;
}
}
class Solution {
public boolean isBalanced(TreeNode root) {
return recur(root) != -1;
}
private int recur(TreeNode root) {
if (root == null) return 0;
int left = recur(root.left);
if(left == -1) return -1;
int right = recur(root.right);
if(right == -1) return -1;
return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
}
}
