二叉树的镜像 2022-02-23 周三

题目

请完成一个函数，输入一个二叉树，该函数输出它的镜像。

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

图片直观些

力扣题目地址

二叉树

二叉排序树

思路

• 关于二叉树的问题，直接反应就是递归。这是很多文章介绍的方法。

• 当然，也有非递归的算法，不过都是通过栈这个结构来模拟递归的思路。既然这样，还不如直接用递归来得直接。压栈，出栈还是很麻烦的。

• 退出条件（递归的首要考虑因素）：root为空，或者没有子节点（left和right都为空）

• 交换：引入一个tempNode，左右子树交换（空的也要交换）

• 递归：只要左右子树不空，那么左右子节点顶替root的位置（作为参数）重复做

• 返回节点：试想只有root，left，right三个节点，交换后，应该返回root。不然的话，编译都通不过。（很多大神的文章漏了这点）

C代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


struct TreeNode* mirrorTree(struct TreeNode* root) {
    // 退出条件: 空结点或者左右子节点都没有
    if ((root == NULL) || ((root->left == NULL)&&(root->right == NULL))) {
        // 这里返回root比返回NULL更合适
        return root;
    }

    // 交换左右结点
    struct TreeNode *tempNode = root->left;
    root->left = root->right;
    root->right = tempNode;

    // 递归：只要不为空，左右就继续
    if (root->left != NULL) {
        mirrorTree(root->left);
    }
    if (root->right != NULL) {
        mirrorTree(root->right);
    }

    // 这行不加的话，编译都通不过
    // 交换了左右子树之后，返回root；
    // 用只有root，left，right三个结点的树来类比就知道应该返回root
    return root;
}

C代码地址

Swift代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public var val: Int
 *     public var left: TreeNode?
 *     public var right: TreeNode?
 *     public init(_ val: Int) {
 *         self.val = val
 *         self.left = nil
 *         self.right = nil
 *     }
 * }
 */
class Solution {
    func mirrorTree(_ root: TreeNode?) -> TreeNode? {
        // 退出条件
        if ((root == nil) || ((root?.left == nil) && (root?.right == nil))) {
            return root
        }

        // 交换
        let temp = root?.left
        root?.left = root?.right
        root?.right = temp

        // 递归
        if let left = root?.left {
            mirrorTree(left)
        }
        if let right = root?.right {
            mirrorTree(right)
        }

        // 返回root
        return root
    }
}

Swift代码

JavaScript代码

解题参考

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var mirrorTree = function(root) {
    // 递归出口
    if (!root) return null;
    // 交换当前左右节点
    [root.left, root.right] = [root.right, root.left];
    // 递归交换左子树的左右节点
    mirrorTree(root.left);
    // 递归交换右子树的左右节点
    mirrorTree(root.right);
    // 返回当前节点给上一级
    return root;
};

JavaScript代码

性能对比

性能对比

C语言的效率优势很大；JavaScript的性能真是堪忧。