4 / \ 2 7 / \ / \ 1 3 6 9to
4 / \ 7 2 / \ / \ 9 6 3 1
<Solution>
這題算是典型的 recursive 的題目
code 如下
Java
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* Definition for a binary tree node. | |
* public class TreeNode { | |
* int val; | |
* TreeNode left; | |
* TreeNode right; | |
* TreeNode(int x) { val = x; } | |
* } | |
*/ | |
class Solution { | |
public TreeNode invertTree(TreeNode root) { | |
if (root == null) { | |
return null; | |
} | |
root.left = invertTree(root.left); | |
root.right = invertTree(root.right); | |
TreeNode tmpN = root.left; | |
root.left = root.right; | |
root.right = tmpN; | |
return root; | |
} | |
} |
Kotlin
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* Example: | |
* var ti = TreeNode(5) | |
* var v = ti.`val` | |
* Definition for a binary tree node. | |
* class TreeNode(var `val`: Int) { | |
* var left: TreeNode? = null | |
* var right: TreeNode? = null | |
* } | |
*/ | |
class Solution { | |
fun invertTree(root: TreeNode?): TreeNode? { | |
return if(root == null) { | |
null | |
} else { | |
root!!.left = root!!.right.also { root!!.right = root!!.left } | |
invertTree(root!!.left) | |
invertTree(root!!.right) | |
root | |
} | |
} | |
} |
當然也有 iterative 的寫法
C++
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* Definition for a binary tree node. | |
* struct TreeNode { | |
* int val; | |
* TreeNode *left; | |
* TreeNode *right; | |
* TreeNode(int x) : val(x), left(NULL), right(NULL) {} | |
* }; | |
*/ | |
class Solution { | |
public: | |
TreeNode* invertTree(TreeNode* root) { | |
queue<TreeNode *> queue; | |
if(root) { | |
queue.push(root); | |
} | |
TreeNode *curN, *tmpN; | |
while(!queue.empty()) { | |
curN = queue.front(); | |
queue.pop(); | |
tmpN = curN->left; | |
curN->left = curN->right; | |
curN->right = tmpN; | |
if(curN->left) { | |
queue.push(curN->left); | |
} | |
if(curN->right) { | |
queue.push(curN->right); | |
} | |
} | |
return root; | |
} | |
}; |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* Definition for a binary tree node. | |
* public class TreeNode { | |
* int val; | |
* TreeNode left; | |
* TreeNode right; | |
* TreeNode(int x) { val = x; } | |
* } | |
*/ | |
class Solution { | |
public TreeNode invertTree(TreeNode root) { | |
Queue<TreeNode> queue = new LinkedList<>(); | |
if(root != null) { | |
queue.add(root); | |
} | |
TreeNode curN, tmpN; | |
while(!queue.isEmpty()) { | |
curN = queue.poll(); | |
tmpN = curN.left; | |
curN.left = curN.right; | |
curN.right = tmpN; | |
if(curN.left != null) { | |
queue.add(curN.left); | |
} | |
if(curN.right != null) { | |
queue.add(curN.right); | |
} | |
} | |
return root; | |
} | |
} |
沒有留言:
張貼留言