Lexi's Leetcode solutions

Posts Tagged ‘前序

这个是left bound, right bound来check if a tree is a BST的变形。愣是没看出来。还是不熟练,桑心。挖坑,要是明天挂了回来接着写。

http://leetcode.com/2010/09/saving-binary-search-tree-to-file.html

Advertisements
Tags: ,

对这类题型其实不够熟悉,写了有15分钟才出来,太差了。总结一下。

BST一般找不到就null了,没办法keep track of走到哪个位置的信息。所以多传两个参数,leftBoundary和rightBoundary,分别表示“当前node为root的子树的left boundary – 当前子树的immediate prev)“和“immediate next”。因为你是top down的往下算,所以左右两边的boundary不断narrow down。当node == null时,此时的最靠近自己的boundary就起作用了,找他们之间最接近x的就行了。

这题和判断一棵树是不是BST是一个套路(后面有对比):

public TreeNode getClosest(TreeNode node, TreeNode leftBoundary, TreeNode rightBoundary, int x) {
  if (node == null)
    return getClosest(leftBoundary, rightBoundary, x);
  if (node.val < x) {
    return getClosest(node.right, node, rightBoundary, x);
  } else {
    return getClosest(node.left, leftBoundary, node, x);
  }
}
private TreeNode getClosest(TreeNode prev, TreeNode next, int x) {
  if (prev == null || next == null)
    return prev == null ? next : prev;
  if (next.val - x < x - prev.val)
    return next;
  else
    return prev;
}

附加:判断一棵树是不是BST,也是一路传下来boundary,不断看当前节点是不是满足上面传下来的左右boundary, 然后往下传的时候narrow down。最开始left, right, node都是null(没有左右节点限制)。

boolean isBST(Node node, Node leftBoundary, Node rightBoundary) {
  if (node == null)
    return true;
  if ((leftBoundary != null && node.val < leftBoundary.val) || (rightBoundary != null && node.val > rightBoundary.val))
    return false;
  if (!isBST(node.left, leftBoundary, node))
    return is BST(node.right, node, rightBoundary);
}

这个题和前几天做的另一道“找二叉树的第n个元素“一样,用到的是pass-count technique:用一个IntWrapper keep track of 线性的index。无论tree怎么走,这个index是不断增加的。

serialize很简单,用#表示null,然后中左右(pre order)的traverse一遍就变成serialize的文件了。

deserialize的话,和preorder一样,怎么来的就怎么populate回去。是#,说明populate null,就不用往下做了;不是的话,继续做;重点是要keep track of current element in the array,就用到了一个Integer wrapper好能把count的这个值一路传下去。需要特别小心的是,这个count要一直增加,不管当前是不是#!

Node deserialize(char[] arr, IntWrapper i) {
  i.val++;//这个不能放if后面!
  if (arr[i.val] == '#')
    return null;
  Node newNode = new Node(arr[i.val]);
  newNode.left = deserialize(arr, i);
  newNode.right = deserialize(arr, i);
  return newNode;
}

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