- Notifications
You must be signed in to change notification settings - Fork24
Open
Labels
Description
Google：我们 90% 的工程师都用你写的软件（Homebrew），但你没法在白板上翻转二叉树，所以翻滚吧，蛋炒饭。
原推截图，至今仍在。 Max Howell 当年吐槽之后 LeetCode 马上加入了这道题。
会了这道题，是不是我们也可以超越世界级大牛了？(狗头保命)
书归正传
首先明确，所谓二叉树的翻转需要满足以下两点：
1.它的左右子树要交换位置。
2.并且左右子树内部的所有子树或是结点都要进行交换位置。
递归
1.从根节点开始，递归的对树进行遍历。
2.从叶子结点开始进行翻转。
3.左右子树都已经翻转后，交换两棵子树的位置即可完成全部的翻转。
constinvertTree=function(root){if(root===null)returnnull// 递归终止条件invertTree(root.left)invertTree(root.right)consttemp=root.leftroot.left=root.rightroot.right=tempreturnroot}
- 时间复杂度: O(n)
- 空间复杂度: O(n)
当然你也可以将上面的 2，3 两个步骤颠倒执行，也就是先交换两棵子树的位置，再对其内部进行翻转。
constinvertTree=function(root){if(root===null)returnnull// 递归终止条件consttemp=root.leftroot.left=root.rightroot.right=tempinvertTree(root.left)invertTree(root.right)returnroot}
BFS
层序遍历遍历二叉树，当根结点出列时，翻转它的左右子树。然后将其左右子节点入列，以便下一层时翻转。
二叉树的层序遍历可参考轻松拿下二叉树的层序遍历
constinvertTree=(root)=>{if(root===null)returnnull;constqueue=[root];while(queue.length){constcur=queue.shift();[cur.left,cur.right]=[cur.right,cur.left];if(cur.left)queue.push(cur.left);if(cur.right)queue.push(cur.right);}returnroot;}