相同的树、对称二叉树、翻转二叉树

[funnycoderstar]

• JavaScript实现LeetCode第100题：相同的树
• JavaScript实现LeetCode第101题：对称二叉树
• JavaScript实现LeetCode第226题：翻转二叉树

这几道题其实很相似，所以可以放在一起理解。

相同的树

题目描述

给定两个二叉树，编写一个函数来检验它们是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

示例 1:

输入:       1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

输出: true

示例 2:

输入:      1          1
          /           \
         2             2

        [1,2],     [1,null,2]

输出: false

示例 3:

输入:       1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

输出: false

思路分析

使用深度优先遍历；

1. 两棵树的当前节点都为null时，返回true
2. 当其中一个是null，另外一个不是 null时，返回 false
3. 当两个都不为null，但是值不相等时，返回 false
4. 上面情况都不满足，则不断递归两颗树的左右子树

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
   // 两棵树的当前节点都为null时，返回true
   if(p == null && q == null) {
        return true;
    }
    // 当其中一个是null，另外一个不是 null时，返回 false
    if(p == null || q == null) {
        return false
    }
    // 当两个都不为null，但是值不相等时，返回 false
    if(p.val !== q.val) {
        return false;
    }
    // 不断递归两颗树的左右子树
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
};

• 时间复杂度：O(n)，n 为树的节点个数，因为每个节点否访问一次
• 空间复杂度：最优情况（完全平衡二叉树）时为 O(log(N))，最坏情况下（完全不平衡二叉树）时为 O(N)，用于维护递归栈。

对称二叉树

题目描述

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

例如，二叉树 [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
 

进阶：

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

思路分析

这个问题可以转化为 两个树在什么情况下互为镜像？

如果同时满足下面的条件，两个树互为镜像：

1. 它们的两个根结点具有相同的值。
2. 每个树的右子树都与另一个树的左子树镜像对称。

/**
 * 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) {
    function isMirror(p, q) {
        if(p == null && q == null) {
            return true;
        }
        if(p == null || q == null) {
            return false;
        }
        if(p.val !== q.val) {
            return false;
        }
        return isMirror(p.left, q.right) && isMirror(p.right, q.left);
    }
    return isMirror(root, root);
};

• 时间复杂度：O(n)，因为我们遍历整个输入树一次，所以总的运行时间为 O(n)，其中 n 是树中结点的总数。
• 空间复杂度：递归调用的次数受树的高度限制。在最糟糕情况下，树是线性的，其高度为 O(n)。因此，在最糟糕的情况下，由栈上的递归调用造成的空间复杂度为 O(n)。

翻转二叉树

题目描述

翻转一棵二叉树。

示例：

输入：

     4
   /   \
  2     7
 / \   / \
1   3 6   9
输出：

     4
   /   \
  7     2
 / \   / \
9   6 3   1

解题思路

递归的交换左右子树。

1. 当节点为 null 的时候直接返回
2. 如果当前结点不为null，那么先将其左右子树进行翻转，然后交换左右子树。
3. 返回值为完成了翻转后的当前结点。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var invertTree = function(root) {
    // 当节点为 null 的时候直接返回
    if(root === null) {
        return root;
    }
    // 如果当前结点不为null，那么先将其左右子树进行翻转，然后交换左右子树
    let right = invertTree(root.right);
    let left = invertTree(root.left);
    root.left = right;
    root.right = left;
    
    // 返回值为完成了翻转后的当前结点
    return root;
};

• 时间复杂度：O(n)，其中 n 是树中节点的个数。在反转之前，不论怎样我们至少都得访问每个节点至少一次，因此这个问题无法做地比 O(n) 更好了。
• 本方法使用了递归，在最坏情况下栈内需要存放 O(h) 个方法调用，其中 h 是树的高度。由于 h $\in$ O(n)，可得出空间复杂度为 O(n)。