五刷 07/2022
Version #1 Recursive
这次写的比较简洁
一个bug就是node.left要设为null
Time O(N)
Space O(N) worst case
Runtime: 1 ms, faster than 78.58% of Java online submissions for Flatten Binary Tree to Linked List.
Memory Usage: 42.3 MB, less than 71.23% of Java online submissions for Flatten Binary Tree to Linked List.
class Solution {
public void flatten(TreeNode root) {
flattenHelper(root);
}
// Returns the last node after flatten
private TreeNode flattenHelper(TreeNode node) {
if (node == null) {
return null;
}
if (node.left == null && node.right == null) {
return node;
}
TreeNode left = flattenHelper(node.left);
TreeNode right = flattenHelper(node.right);
if (left != null) {
left.right = node.right;
node.right = node.left;
node.left = null;
}
return right == null ? left : right;
}
}
四刷 05/2022
Version #1 Recursive
这里代码有冗余的
因为如果leftLast是Null 的话，当前node.right已经是右子树的root了不需要再更改了，所以只需要返回node.right == null ? node : rightLast
只有当左子树不为空的时候才需要把它插入到node和右子树之间
这次代码写得不好，参考前面写的
Runtime: 0 ms, faster than 100.00% of Java online submissions for Flatten Binary Tree to Linked List.
Memory Usage: 42.7 MB, less than 47.36% of Java online submissions for Flatten Binary Tree to Linked List.
/**
* 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 void flatten(TreeNode root) {
helper(root);
}
// Returns the last node after the subtree is flatterned
private TreeNode helper(TreeNode node) {
if (node == null) {
return null;
}
TreeNode prev = node;
TreeNode last = node;
TreeNode leftLast = helper(node.left);
TreeNode rightLast = helper(node.right);
TreeNode rightRoot = node.right;
if (leftLast != null) {
prev.right = node.left;
last = leftLast;
prev = leftLast;
}
if (rightLast != null) {
prev.right = rightRoot;
last = rightLast;
}
node.left = null;
return last;
}
}
Version #2 Iterative
注意这里是先push right 再push left
Runtime: 2 ms, faster than 13.01% of Java online submissions for Flatten Binary Tree to Linked List.
Memory Usage: 42.6 MB, less than 53.16% of Java online submissions for Flatten Binary Tree to Linked List.
/**
* 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 void flatten(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
TreeNode prev = null;
while (!stack.isEmpty()) {
TreeNode curr = stack.pop();
if (prev != null) {
prev.left = null;
prev.right = curr;
}
if (curr.right != null) {
stack.push(curr.right);
}
if (curr.left != null) {
stack.push(curr.left);
}
prev = curr;
}
}
}
三刷
Version #2 Iterative
71.35 %
class Solution {
public void flatten(TreeNode root) {
// Inorder traversal while keeping track of prev node
// link to prev when push
Deque<TreeNode> deque = new ArrayDeque<>();
TreeNode curr = root;
TreeNode prev = null;
while (curr != null) {
if (curr.right != null) {
deque.addFirst(curr.right);
}
if (curr.left != null) {
deque.addFirst(curr.left);
}
if (prev != null) {
prev.right = curr;
prev.left = null;
}
prev = curr;
curr = deque.isEmpty() ? null : deque.removeFirst();
}
}
}
Version #1 Recursive
三刷
没有考虑rightTail是Null 以及 leftTail & rightTail都是null的情况
需要都考虑全
root, left, right三个部分都有可能是Null
24.56 %
public class Solution {
public void flatten(TreeNode root) {
flattenHelper(root);
}
//return the tail of the flatten partial of tree
private TreeNode flattenHelper(TreeNode root) {
if (root == null) return null;
if (root.left == null && root.right == null) return root;
TreeNode leftTail = flattenHelper(root.left);
TreeNode rightTail = flattenHelper(root.right);
if (root.left != null) {
leftTail.right = root.right;
root.right = root.left;
root.left = null;
}
return rightTail == null ? leftTail : rightTail;
}
}
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/
public class Solution {
/**
* @param root: a TreeNode, the root of the binary tree
* @return: nothing
*/
public void flatten(TreeNode root) {
// write your code here
helper(root);
}
//given the root
//return the last node of the linkedlist
public TreeNode helper(TreeNode root) {
if(root == null) {
return null;
}
TreeNode lastLeft = helper(root.left);
TreeNode lastRight = helper(root.right);
System.out.println("root.left = " + root.left.val + " lastLeft = " + lastLeft.val);
if (root.left != null) {
lastLeft.right = root.right;
root.right = root.left;
root.left = null;
}
if (root.right != null) {
return lastRight;
}
if (root.left != null) {
return lastLeft;
}
return root;
}
}
二刷
public class Solution {
/**
* @param root: a TreeNode, the root of the binary tree
* @return: nothing
*/
public void flatten(TreeNode root) {
// write your code here
helper(root);
}
//given the root
//return the last node of the linkedlist
public TreeNode helper(TreeNode root) {
if(root == null) {
return null;
}
TreeNode lastLeft = helper(root.left);
TreeNode lastRight = helper(root.right);
//System.out.println("root.left = " + root.left.val + " lastLeft = " + lastLeft.val);
if (root.left == null) {
if (root.right != null) return lastRight;
return root;
}
lastLeft.right = root.right;
root.right = root.left;
root.left = null;
if (lastRight != null) return lastRight;
return lastLeft;
}
}
No comments:
Post a Comment