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

Posted by: lexigrey on: July 17, 2013

• In: leetcode
• 2 Comments

可算能自己做出来一道。。这个一开始被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: tree, 前序