226. 翻转二叉树
题目描述
给你一棵二叉树的根节点 root
,翻转这棵二叉树,并返回其根节点。
示例 1:
输入:root = [4,2,7,1,3,6,9] 输出:[4,7,2,9,6,3,1]
示例 2:
输入:root = [2,1,3] 输出:[2,3,1]
示例 3:
输入:root = [] 输出:[]
提示:
- 树中节点数目范围在
[0, 100]
内 -100 <= Node.val <= 100
方法一:递归
递归的思路很简单,就是交换当前节点的左右子树,然后递归地交换当前节点的左右子树。
时间复杂度
java
class Solution {
public TreeNode invertTree(TreeNode root) {
dfs(root);
return root;
}
private void dfs(TreeNode root) {
if (root == null) {
return;
}
TreeNode t = root.left;
root.left = root.right;
root.right = t;
dfs(root.left);
dfs(root.right);
}
}
cpp
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
function<void(TreeNode*)> dfs = [&](TreeNode* root) {
if (!root) {
return;
}
swap(root->left, root->right);
dfs(root->left);
dfs(root->right);
};
dfs(root);
return root;
}
};
ts
function invertTree(root: TreeNode | null): TreeNode | null {
const dfs = (root: TreeNode | null) => {
if (root === null) {
return;
}
[root.left, root.right] = [root.right, root.left];
dfs(root.left);
dfs(root.right);
};
dfs(root);
return root;
}
python
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
def dfs(root):
if root is None:
return
root.left, root.right = root.right, root.left
dfs(root.left)
dfs(root.right)
dfs(root)
return root
方法二
java
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode l = invertTree(root.left);
TreeNode r = invertTree(root.right);
root.left = r;
root.right = l;
return root;
}
}
cpp
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (!root) {
return root;
}
TreeNode* l = invertTree(root->left);
TreeNode* r = invertTree(root->right);
root->left = r;
root->right = l;
return root;
}
};
ts
function invertTree(root: TreeNode | null): TreeNode | null {
if (!root) {
return root;
}
const l = invertTree(root.left);
const r = invertTree(root.right);
root.left = r;
root.right = l;
return root;
}
python
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if root is None:
return None
l, r = self.invertTree(root.left), self.invertTree(root.right)
root.left, root.right = r, l
return root