Invert a binary tree.
Example:
Input:
4 / \ 2 7 / \ / \ 1 3 6 9
Output:
4 / \ 7 2 / \ / \ 9 6 3 1
Trivia:
This problem was inspired by this original tweet by Max Howell:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.
Solution: Recursion
Recursive invert the left and right subtrees and swap them.
Time complexity: O(n)
Space complexity: O(h)
C++
1 2 3 4 5 6 7 8 9 10 11 |
// Author: Huahua class Solution { public: TreeNode* invertTree(TreeNode* root) { if (!root) return nullptr; TreeNode* tmp = root->right; root->right = invertTree(root->left); root->left = invertTree(tmp); return root; } }; |
Python3
1 2 3 4 5 6 |
# Author: Huahua class Solution: def invertTree(self, root: TreeNode) -> TreeNode: if not root: return None root.left, root.right = self.invertTree(root.right), self.invertTree(root.left) return root |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment