Lexi's Leetcode solutions

[leetcode] Flatten Binary Tree to Linked List | 树按preorder给扯平了

Posted on: July 17, 2013

可算能自己做出来一道。。这个一开始被pre order给distract了,然后实在没招了就使出惯用的bottom up,然后一下就想出来了。不过最后逻辑分情况讨论有点复杂,忍了。

private Data getData(TreeNode root) {
  if (root == null)
    return null;
  Data left = getData(root.left);
  Data right = getData(root.right);
  root.left = null;
  if (left != null) {
    root.right = left.start;
    if (right != null) {
      left.end.right = right.start;
      return new Data(root, right.end);
    } else {
      return new Data(root, left.end);
    }
  } else {
    if (right != null) {
      root.right = right.start;
      return new Data(root, right.end);
    } else
      return new Data(root, root);
    }
  }
}

————————————十月份重做——————————-
按pre order,keep一个prev reference就行了。还是那个顺次的pattern。注意这是in place的改动右孩子,同时左孩子清空,所以要把他们先暂存下来。

	public void flatten(TreeNode root) {
		flatten(root, new TreeNode[1]);
	}
	private void flatten(TreeNode root, TreeNode[] prev) {
		if (root == null)
			return;
		if (prev[0] == null) {
			prev[0] = root;
		} else {
			prev[0].right = root;
			prev[0] = root;
		}
		TreeNode leftBeforeModification = root.left;
		TreeNode rightBeforeModification = root.right;
		root.left = null;
		flatten(leftBeforeModification, prev);
		flatten(rightBeforeModification, prev);
	}
Tags: ,

2 Responses to "[leetcode] Flatten Binary Tree to Linked List | 树按preorder给扯平了"

我是用preorder把tree展平到left child,然后再iterative way to move to the right child.会不会更自然些。

我写的
public void flatten(TreeNode root) {
if (root != null) {
while (root.left != null || root.right != null) {
if (root.left != null) {
TreeNode rightmost = root.left;
TreeNode right = rightmost;
TreeNode temp = root.right;
while (rightmost.right != null) {
rightmost = rightmost.right;
}
rightmost.right = temp;
root.right = right;
root.left = null;
root = root.right;
} else
root = root.right;
}
}
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

Blog Stats

  • 222,234 hits
July 2013
M T W T F S S
1234567
891011121314
15161718192021
22232425262728
293031  
%d bloggers like this: