leetcode101：对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

进阶：

你可以运用递归和迭代两种方法解决这个问题吗？

附赠leetcode地址：leetcode

递归

比较二叉树的 前序遍历 和 对称前序遍历 来判断是不是对称的。

前序遍历：根-左-右

对称前序遍历：根-右-左

/**
 * 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

递归

/**
 * 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
}

解答：

一棵二叉树对称，则需要满足：根的左右子树是镜像对称的

也就是说，每棵树的左子树都和另外一颗树的右子树镜像对称，左子树的根节点值与右子树的根节点值相等

所以，我们需要比较：

左右子树的根节点值是否相等
左右子树是否镜像对称

边界条件：

左右子树都为 null 时，返回 true
左右子树有一个 null 时，返回 false

解法一：递归

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)
};

复杂度分析：

时间复杂度：O(n)
空间复杂度：O(n)

解法二：迭代

利用栈来记录比较的过程，实际上，递归就使用了调用栈，所以这里我们可以使用栈来模拟递归的过程

首先根的左右子树入栈
将左右子树出栈，比较两个数是否互为镜像
如果左右子树的根节点值相等，则将左子树的 left 、右子树的 right 、左子树的 right 、右子树的 left 依次入栈
继续出栈（一次出栈两个进行比较）…….

依次循环出栈入栈，直到栈为空

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
};

复杂度分析：

时间复杂度：O(n)
空间复杂度：O(n)

leetcode

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
	}
}

Navigation Menu

Repository navigation

leetcode101：对称二叉树 #53

递归

解法一：递归

解法二：迭代

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

leetcode101：对称二叉树 #53

Description

Activity

plane-hjh commented on May 27, 2020

递归

7777sea commented on May 27, 2020

fanefanes commented on May 27, 2020

plane-hjh commented on May 27, 2020

jasonting5 commented on May 27, 2020

sisterAn commented on May 27, 2020

解法一：递归

解法二：迭代

luweiCN commented on May 27, 2020

AnranS commented on Nov 20, 2020

xiaowuge007 commented on Apr 27, 2021

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions