226. Invert Binary Tree
latest version
T : O(n)
S: O(n)
思路 左邊接右邊dfs, 右邊接左邊 dfs
```java
class Solution {
public TreeNode invertTree(TreeNode root) {
return dfs(root);
}
private TreeNode dfs(TreeNode node) {
if (node == null) {
return null;
}
TreeNode root = new TreeNode(node.val);
root.left = dfs(node.right);
root.right = dfs(node.left);
return root;
}
}
```
左右對調就是了, like swapping
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) { //termainator
return root;
}
// like swap - process
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
invertTree(root.left); // drill dwon
invertTree(root.right); // drill dwon
return root;
}
}
or like this
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode temp = root.left;
root.left = invertTree(root.right);
root.right = invertTree(temp);
return root;
}
Previous889. Construct Binary Tree from Preorder and Postorder TraversalNext116. Populating Next Right Pointers in Each Node
Last updated
Was this helpful?