leetcode101：对称二叉树 #53
Comments
递归比较二叉树的 前序遍历 和 对称前序遍历 来判断是不是对称的。 前序遍历：根-左-右 对称前序遍历：根-右-左 /**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
const isSymmetric = (root) => {
return isSymmetrical(root, root)
};
const isSymmetrical = (r1, r2) => {
if(r1 === null && r2 === null) return true
if(r1 === null || r2 === null) return false
if(r1.val !== r2.val) return false
return isSymmetrical(r1.left, r2.right) && isSymmetrical(r1.right, r2.left)
} |
/**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isSymmetric = function(root) {
if(root === null) return true;
function isEqual(left, right){
if(left === null && right === null) return true;
if(left === null || right === null) return false;
if(left.val !== right.val) return false;
return isEqual(left.left, right.right) && isEqual(left.right, right.left)
}
return isEqual(root.left, root.right)
}; |
|
递归 /**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isSymmetric = function(root) {
if(root === null) return true;
function isEqual(left, right){
if(left === null && right === null) return true;
if(left === null || right === null) return false;
if(left.val !== right.val) return false;
return isEqual(left.left, right.right) && isEqual(left.right, right.left)
}
return isEqual(root.left, root.right)
}迭代 /**
* Definition for a binary tree node.
* function TreeNode(val) {
* this.val = val;
* this.left = this.right = null;
* }
*/
/**
* @param {TreeNode} root
* @return {boolean}
*/
var isSymmetric = function(root) {
if(root === null) return true;
const list = []
list.push([root.left, root.right])
while(list.length>0){
const track = list.pop()
if(track[0] !== null && track[1] !== null){
if(track[0].val !== track[1].val) return false;
list.push([track[0].left, track[1].right])
list.push([track[0].right, track[1].left])
}else if((track[0] !== null && track[1] === null) || (track[0] === null && track[1] !== null)) {
return false;
}
}
return true
} |
@fanefanes 这个迭代学到了，感谢~ |
var isSymmetric = function(root) {
// 用迭代方法实现
if (!root) {
return true
}
let queue = []
queue.push(root)
queue.push(root)
while (queue.length > 0) {
let p1 = queue.shift(),
p2 = queue.shift()
if (!p1 && !p2) continue
if (!p1 || !p2) return false
if (p1.val !== p2.val) return false
queue.push(p1.left)
queue.push(p2.right)
queue.push(p1.right)
queue.push(p2.left)
}
return true
} |
|
解答： 一棵二叉树对称，则需要满足：根的左右子树是镜像对称的 也就是说，每棵树的左子树都和另外一颗树的右子树镜像对称，左子树的根节点值与右子树的根节点值相等 所以，我们需要比较：
边界条件：
解法一：递归const isSymmetric = function(root) {
if(!root) return true
var isEqual = function(left, right) {
if(!left && !right) return true
if(!left || !right) return false
return left.val === right.val
&& isEqual(left.left, right.right)
&& isEqual(left.right, right.left)
}
return isEqual(root.left, root.right)
};复杂度分析：
解法二：迭代利用栈来记录比较的过程，实际上，递归就使用了调用栈，所以这里我们可以使用栈来模拟递归的过程
依次循环出栈入栈，直到栈为空 const isSymmetric = function(root) {
if(!root) return true
let stack = [root.left, root.right]
while(stack.length) {
let right = stack.pop()
let left = stack.pop()
if(left && right) {
if(left.val !== right.val) return false
stack.push(left.left)
stack.push(right.right)
stack.push(left.right)
stack.push(right.left)
} else if(left || right) {
return false
}
}
return true
};复杂度分析：
|
var isSymmetric = function (root) {
if (root === null) return true;
function symmetric(left, right) {
if (left === null && right === null) {
return true;
} else if (left !== null && right !== null) {
return (
left.val === right.val &&
symmetric(left.left, right.right) &&
symmetric(left.right, right.left)
);
} else {
return false;
}
}
return symmetric(root.left, root.right);
}; |
var isSymmetric = function(root) {
if(!root) return true;
let quene = [root];
let tmpQueue = [];
while(quene.length) {
let len = quene.length;
for(let i = 0;i<len;i++) {
let node = quene.shift();
if(node.left) {
quene.push(node.left);
tmpQueue.push(node.left.val);
} else {
tmpQueue.push('#');
}
if(node.right) {
quene.push(node.right);
tmpQueue.push(node.right.val);
} else {
tmpQueue.push('#');
}
}
let left = 0, right = tmpQueue.length - 1;
while(left < right) {
if(tmpQueue[left++] !== tmpQueue[right--]) return false;
}
tmpQueue = [];
}
return true;
}; |
function symmetryTree_2(root) {
if(!root){return false}
if(!root.left && !root.right){return true}
if(!root.left || !root.right){return false}
if(root.left && root.right){
let arr = [root.left,root.right];
while (arr.length>0){
let left = arr.shift();
let right = arr.pop();
if(!left && !right){
continue;
}
if((left && !right) || (right && !right) || (left.id !== right.id)){
return false
}
arr.unshift(left.left);
arr.push(right.right);
arr.unshift(left.right);
arr.push(right.left);
}
return true
}
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树
[1,2,2,3,4,4,3]是对称的。但是下面这个
[1,2,2,null,3,null,3]则不是镜像对称的:进阶：
你可以运用递归和迭代两种方法解决这个问题吗？
附赠leetcode地址：leetcode
The text was updated successfully, but these errors were encountered: