翻转一棵二叉树。
输入:
4
/ \
2 7
/ \ / \
1 3 6 9
输出:
4
/ \
7 2
/ \ / \
9 6 3 1
这个问题是受到 Max Howell 的 原问题 启发的 :
谷歌:我们90%的工程师使用您编写的软件(Homebrew),但是您却无法在面试时在白板上写出翻转二叉树这道题,这太糟糕了。
使用队列,当队列中有元素时,则对依次出列,并对当前元素通过中间变量进行左右交换,若交换后的元素存在,则再进入队列。
const invertTree = function(root) {
if (!root) return null
const queue = [root]
while(queue.length){
let node = queue.shift()
let temp = node.left
node.left = node.right
node.right = temp
if (node.left)
queue.push(node.left)
if (node.right)
queue.push(node.right)
}
return root
};
const invertTree = function(root) {
if (!root) return null
const queue = [root]
while(queue.length){
let node = queue.shift();
[node.left, node.right] = [node.right, node.left]
if (node.left)
queue.push(node.left)
if (node.right)
queue.push(node.right)
}
return root
};
当前函数进行左右节点交换,若左节点或右节点存在,则再次对存在节点调用invertTree函数。需要注意的是当根节点为空时,则直接返回null。
const invertTree = function(root) {
if (!root) return null;
[root.left, root.right] = [root.right, root.left]
if (root.left) invertTree(root.left)
if (root.right) invertTree(root.right)
return root
};
题目来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/invert-binary-tree
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
扫码关注腾讯云开发者
领取腾讯云代金券
Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号:粤B2-20090059 深公网安备号 44030502008569
腾讯云计算(北京)有限责任公司 京ICP证150476号 | 京ICP备11018762号 | 京公网安备号11010802020287
Copyright © 2013 - 2025 Tencent Cloud.
All Rights Reserved. 腾讯云 版权所有