# 二叉树的镜像📕

# 题目描述

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

例如🌰:

# 解题思路

  1. 根节点不需要变;
  2. 二叉树的左子树的节点与右子树的节点进行交换;
  3. 遍历交换子节点.

# coding

解法一

我开始的想法是, 每次都重新生成一个新的节点然后赋值.但实际上这样解法不是最优的, 每次都产生多余的对象.

/*
* 二叉树结点类
*/
class Node {
    constructor(value, left = null, right = null) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}
/*
* 传入一个二叉树, 返回二叉树的镜像
* param {Node} 二叉树
* return {NOde} 二叉树镜像
*/
function mirrorBinaryTree(node) {
    if (!node) return null
    let tree = new Node(node.value) // 生成一个新的节点
    tree.left = mirrorBinaryTree(node.right) // 新节点的左子树为原节点的右子树
    tree.right = mirrorBinaryTree(node.left)
    return tree
}
const tree3 = new Node(8, new Node(6, new Node(5), new Node(7)), new Node(10, new Node(9), new Node(11)))
console.log(tree3)
console.log(mirrorBinaryTree(tree3))

解法二

可以直接找进行左右节点的交换:

/*
* 传入一个二叉树, 返回二叉树的镜像
* param {Node} 二叉树
* return {NOde} 二叉树镜像
*/
function mirrorBinaryTree(node) {
    if (!node) return null
    let left = node.left
    node.left = node.right
    node.right = left
    if (node.left) mirrorBinaryTree(node.left)
    if (node.right) mirrorBinaryTree(node.right)
}
const tree3 = new Node(8, new Node(6, new Node(5), new Node(7)), new Node(10, new Node(9), new Node(11)))
mirrorBinaryTree(tree3)
console.log(tree3)
阅读全文