2017年11月30日 星期四

[LeetCode] 226. Invert Binary Tree

轉自LeetCode

Invert a binary tree.
     4
   /   \
  2     7
 / \   / \
1   3 6   9
to
     4
   /   \
  7     2
 / \   / \
9   6 3   1

<Solution> 
這題算是典型的 recursive 的題目

code 如下

Java
/**
* 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
/**
* 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++
/**
* 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;
}
};
Java
/**
* 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;
}
}

沒有留言:

張貼留言