101 对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

题解

可以使用递归方法和非递归方法来解答此题

递归解法

这题是要整体判断左右子树是不是镜像而不是每个子树的左右节点。我们要用后序遍历来处理，为什么要用后序遍历来处理呢，因为要把处理的步骤放到最后，相当于一种回溯方法。判断完子节点后要返回到上一层继续判断。

我们在写递归程序的时候要想好参数， 单层逻辑，以及终止条件。

入参参数应该是两个节点，分别表示当前处理到的左子树的节点和右子树上的节点。

终止条件好些：

var isSymmetricSingle = function(left, right) {
    if(!left && !right) {
        // 同时为空
        return true
    } else if ((left && !right) || (left && !right)) {
        //有一个为空，直接false
        return false
    } else if (left.val !== right.val) {
        //同时不为空，且值不相同，返回false
        return false
    }
}

单层的递归

//回溯到最顶层返回，其实相当于后序递归
const inner = isSymmetricRecur(left.right, right.left)
const outer = isSymmetricRecur(left.left, right.right)

return inner && outer

整体的解答：

var isSymmetricRecursive = function (root) {
    // 要比较的是两棵树的左右子树
    var isSymmetricRecur = function (left, right) {
        // 返回值是bool
        if (!left && !right) {
            //都是空的满足
            return true
        } else if ((left && !right) || (!left && right)) {
            //有一个是空的
            return false
        } else if (left.val !== right.val) {
            return false
        }
        const inner = isSymmetricRecur(left.right, right.left)
        const outer = isSymmetricRecur(left.left, right.right)

        return inner && outer
    }
    return isSymmetricRecur(root.left, root.right)
}

非递归解法

如果是非递归解法，可以利用栈来表示，同时压入左子树的左节点，右子树的右节点和左子树的右节点和右子树的左节点。这里其实利用了先序遍历的非递归方法。

var isSymmetricStack = function (root) {
    //如果按照栈来的话
    const stack = []
    if (!root) {
        return true
    }
    stack.push(root.left)
    stack.push(root.right)
    var result = true
    while (stack.length) {
        const left = stack.pop()
        const right = stack.pop()

        if ((left && !right) || (!left && right)) {
            result = false
        } else if (left && right && left.val !== right.val) {
            result = false
        }

        stack.push(left.left, right.right)
        stack.push(left.right, right.left)
    }

    return result
}