101. Symmetric Tree

[Tcdian]

101. Symmetric Tree

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

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

    1
   / \
  2   2
 / \ / \
3  4 4  3

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

    1
   / \
  2   2
   \   \
   3    3

Follow up:

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

[Tcdian]

Solution 1 ( DFS 递归 )

• JavaScript Solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    if (root === null) {
        return true;
    }
    return isSymmetricEqual(root.left, root.right);
};

function isSymmetricEqual(treeNode1, treeNode2) {
    if (treeNode1 === null && treeNode2 === null) {
        return true;
    }
    if (treeNode1 === null || treeNode2 === null) {
        return false;
    }
    return treeNode1.val === treeNode2.val
        && isSymmetricEqual(treeNode1.left, treeNode2.right)
        && isSymmetricEqual(treeNode1.right, treeNode2.left);
}

• TypeScript Solution

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

var isSymmetric = function(root: TreeNode | null): boolean {
    if (root === null) {
        return true;
    }
    return isSymmetricEqual(root.left, root.right);
};

function isSymmetricEqual(treeNode1: TreeNode | null, treeNode2: TreeNode | null): boolean {
    if (treeNode1 === null && treeNode2 === null) {
        return true;
    }
    if (treeNode1 === null || treeNode2 === null) {
        return false;
    }
    return treeNode1.val === treeNode2.val
        && isSymmetricEqual(treeNode1.left, treeNode2.right)
        && isSymmetricEqual(treeNode1.right, treeNode2.left);
}

Solution 2 ( DFS 迭代 )

• JavaScript Solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    if (root === null) {
        return true;
    }
    let stack = [[root.left, root.right]];
    while(stack.length !== 0) {
        const [treeNode1, treeNode2] = stack.pop();
        if (treeNode1 === null && treeNode2 === null) {
            continue;
        }
        if (treeNode1 === null || treeNode2 === null) {
            return false;
        }
        if (treeNode1.val !== treeNode2.val) {
            return false;
        }
        stack.push([treeNode1.left, treeNode2.right], [treeNode1.right, treeNode2.left]);
    }
    return true;
};

• TypeScript Solution

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

var isSymmetric = function(root: TreeNode | null): boolean {
    if (root === null) {
        return true;
    }
    let stack: [TreeNode | null, TreeNode | null][] = [[root.left, root.right]];
    while(stack.length !== 0) {
        const [treeNode1, treeNode2] = stack.pop() as [TreeNode | null, TreeNode | null];
        if (treeNode1 === null && treeNode2 === null) {
            continue;
        }
        if (treeNode1 === null || treeNode2 === null) {
            return false;
        }
        if (treeNode1.val !== treeNode2.val) {
            return false;
        }
        stack.push([treeNode1.left, treeNode2.right], [treeNode1.right, treeNode2.left]);
    }
    return true;
};

Solution 3 ( BFS )

• JavaScript Solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    if (root === null) {
        return true;
    }
    let queue = [[root.left, root.right]];
    while(queue.length !== 0) {
        const [treeNode1, treeNode2] = queue.shift();
        if (treeNode1 === null && treeNode2 === null) {
            continue;
        }
        if (treeNode1 === null || treeNode2 === null) {
            return false;
        }
        if (treeNode1.val !== treeNode2.val) {
            return false;
        }
        queue.push([treeNode1.left, treeNode2.right], [treeNode1.right, treeNode2.left]);
    }
    return true;
};

• TypeScript Solution

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isSymmetric = function(root) {
    if (root === null) {
        return true;
    }
    let queue = [[root.left, root.right]];
    while(queue.length !== 0) {
        const [treeNode1, treeNode2] = queue.shift();
        if (treeNode1 === null && treeNode2 === null) {
            continue;
        }
        if (treeNode1 === null || treeNode2 === null) {
            return false;
        }
        if (treeNode1.val !== treeNode2.val) {
            return false;
        }
        queue.push([treeNode1.left, treeNode2.right], [treeNode1.right, treeNode2.left]);
    }
    return true;
};