二叉树的镜像|博客系列
# 二叉树的镜像📕
# 题目描述
请完成一个函数，输入一个二叉树，该函数输出它的镜像。
例如🌰：
# 解题思路
- 根节点不需要变;
- 二叉树的左子树的节点与右子树的节点进行交换;
- 遍历交换子节点.
# 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)
@前端进阶之旅: 代码已经复制到剪贴板
