广度优先遍历 BFS
解题思路
使用 层序遍历 遍历二叉树；
交换当前节点的左右子节点即可，遍历完成后，则翻转完成；
复杂度
-
时间复杂度：
O(n)，每个点进队出队各一次，故渐进时间复杂度为O(n)； -
空间复杂度：
O(n)，队列中元素的个数不超过 n 个，故渐进空间复杂度为O(n)；
代码实现
var invertTree = function (root) {
if (root === null) return root;
const queue = [root]; // 声明队列用于存储后续数据
while (queue.length) {
let len = queue.length;
while (len--) {
// 将本次操作的结点出队
const node = queue.shift();
// 交换左右节点
let tmp = node.right;
node.right = node.left;
node.left = tmp;
node.left && queue.push(node.left);
node.right && queue.push(node.right);
}
}
return root;
};
深度优先遍历 DFS
复杂度
-
时间复杂度：
O(N)，其中 N 为二叉树节点的数目，遍历二叉树中的每一个节点，交换其两棵子树； -
空间复杂度：
O(N)，使用的空间由递归栈的深度决定，它等于当前节点在二叉树中的高度；- 在平均情况下，二叉树的高度为
O(logN)； - 在最坏情况下，树形成链状高度为
O(N)；
- 在平均情况下，二叉树的高度为
代码实现
var invertTree = function (root) {
if (root === null) return root;
// 交换当前节点的左右子树
[root.left, root.right] = [invertTree(root.right), invertTree(root.left)];
// let tmp = invertTree(root.right);
// root.right = invertTree(root.left);
// root.left = tmp;
return root;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 111. 二叉树的最小深度
上一篇
评论
