Lexi's Leetcode solutions

Posts Tagged ‘tree

思路:

  1. 因为没有random access,所以用in order的方式,一个一个遍历element,然后assign给parent
  2. 平时正常array convert bst都是用pre order的方式,root算好,然后left=.., right =…
  3. 一般你做树的bottom up是post order,left做出来,right做出来,root取决于这两个值
  4. 这里为什么要in order呢? 左,中,右的方式,正好是sorted。所以每次做完子树,然后下一个节点就是下一个位置。但是什么时候是个头呢,因为h.next会一直存在的,但是你的子树怎么知道什么时候返回到上一层?所以就要用p, q两个指针了,p代表当前sub list的头,q是尾。但是不要真的用他们来random access,就是用来stop就行了。
public TreeNode sortedListToBST(ListNode head) {
    int len = 0;
    ListNode dummy = head;
    while (dummy != null) {
       len++;
    dummy = dummy.next;
    }
    ListNode[] curr = new ListNode[1];
    curr[0] = head;
    return convert(curr, 0, len - 1);
}
private TreeNode convert(ListNode[] curr, int p, int q) {
    if (p > q)
        return null;
    int mid = (p + q) / 2;
    TreeNode left = convert(curr, p, mid - 1);
    TreeNode root = new TreeNode(curr[0].val);
    curr[0] = curr[0].next;
    TreeNode right = convert(curr, mid + 1, q);
    root.left = left;
    root.right = right;
    return root;
}
Advertisements
Tags: , , ,

算法:

  • arch代表穿过当前节点的路径(左边一支儿+自己节点+右边一支儿)。
  • 注意树的节点可以是负数,所以arch不一定是最长的。
  • 每次return以root(当前节点)开头最大的单只path sum。
  • res[]就是一个存result的reference object,java不支持c++那种直接&传reference,
    所以要么用个长度为一的数组,要么写个wrapper。还是用数组简单。
  • update res[0],用arch和以自己开头一支儿的比,谁大就把res[0] update成谁。
public int maxPathSum(TreeNode root) {
    int[] res = new int[1];
    res[0] = Integer.MIN_VALUE;
    maxPath(root, res);
    return res[0];
}
private int maxPath(TreeNode root, int[] res) {
    if (root == null)
        return 0;
    int left = maxPath(root.left, res);//左边一支儿(不算自己)
    int right = maxPath(root.right, res);
    int arch = left + right + root.val; //穿过自己
    int single = Math.max(root.val, Math.max(left, right) + root.val);
    //(算上自己)
    res[0] = Math.max(res[0], Math.max(arch, single));//update结果
    return single;
}
Tags: ,

树的dfs变形,还是两个list来回倒。但是这题上来就写还不行,真心得在纸上画一画才能看出来规律。一开始觉得keep一个boolean,正常顺序就加后面,逆序就加前面呗,但是没注意到parent其实很可能已经不是原来顺序的了。画个四层的树就能看出来咋回事了。还有一个小bug就是最开始的boolean reverse应该是true,因为他代表了“parent下面一层要什么顺序”,而不是parent本身是什么顺序。所以还是,变量的物理意义一定要搞清再写!

public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
    ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
    if (root == null)
        return result;
    ArrayList<TreeNode> parents = new ArrayList<TreeNode>();
    boolean reverse = true;//first children line is reversed
    parents.add(root);
    while (!parents.isEmpty()) {
        ArrayList<TreeNode> children = new ArrayList<TreeNode>();
        for (int i = parents.size() - 1; i >= 0; i--) {
            TreeNode parent = parents.get(i);
            if (!reverse) {// the children list wants to be normal order
                if (parent.left != null)
                    children.add(parent.left);
                if (parent.right != null)
                    children.add(parent.right);
            } else { //the children wants to be right to left
                if (parent.right != null)
                    children.add(parent.right);
                if (parent.left != null)
                    children.add(parent.left);
            }
        }
        result.add(convertToIntegerList(parents));
        reverse = !reverse;
        parents = children;
    }
    return result;
}
Tags: ,

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

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

Tags: ,
Tags:

用两个stack O(n)的方法:

  1. 一个stack s1 push root。
  2. 一边pop s1进s2,一边把pop的left, right push进s1(先左后右,这先进s2的是右边,左边在s2靠前部分,所以最后先print出来)
  3. 这样最后s2就是一个正好从上到下是post order的traversal,一边pop一边print就行了。
public void postOrderTwoStacks(TreeNode root) {
  Stack<TreeNode> s1 = new Stack<TreeNode>();
  Stack<TreeNode> s2 = new Stack<TreeNode>();
  s1.push(root);
  while (!s1.isEmpty()) {
    TreeNode pop = s1.pop();
    s2.push(pop);
    if (pop.left != null)
      s1.push(pop.left);
    if (pop.right != null)
      s1.push(pop.right);
  }
  while (!s2.isEmpty()) {
    System.out.print(s2.pop().val + ", ");
  }
}

用一个stack O(h)的方法:

  1. 一个stack,先push root
  2. keep一个prev variable表示刚才试过的node(在stack里尝试来着,不管最后是否把它pop出去了),一直在更新。
  3. stack.peek() == curr,每次用curr和prev比较
    • 如果prev是空或者prev是curr的parent,说明在top down的traverse,这时候可不能print prev(那就变成preorder了);而应该push curr的左子,木有才push右子,全都木有说明curr是leaf,就pop print就行了。
    • 如果prev是curr的左子,说明在从左下角往上traverse,这时若curr有右子,则push右子(应该traverse右子)- prev应该是已经pop出来的了。
    • 如果prev是curr的右子,说明从右下角往左上traverse,这时直接pop print curr就行了,因为这时root也该出来了。
public void postOrder(TreeNode root) {
  Stack<TreeNode> s = new Stack<TreeNode>();
  s.push(root);
  TreeNode prev = null;
  while (!s.isEmpty()) {
    TreeNode curr = s.peek();
    if (prev == null || prev.left == curr || prev.right == curr) { // top down
      if (curr.left != null)
        s.push(curr.left);
      else if (curr.right != null)
        s.push(curr.right);
      else {// is leaf
        popAndPrint(s, curr);
      }
    } else if (prev == curr.left) { // from left child to parent
      if (curr.right != null)
        s.push(curr.right);
      else {
        popAndPrint(s, curr);
      }
    } else { // prev.right == curr, from right child to parent
      popAndPrint(s, curr);
    }
    prev = curr;
  }
}
private void popAndPrint(Stack<TreeNode> s, TreeNode curr) {
  System.out.print(curr.val + ", ");
  s.pop();
}

经典题,注意balanced的定义:左右子树都balance,且高度差<=1。所以下面这个也是balanced的,即使a的做右子树都不是完全树。

    a
   / \ 
  b   d
 /     \
c       e

唯一的trick:不用生成新的data structure来保存“boolean isBalanced, int height”,直接用height = -1表示不平衡就行。

public boolean isBalanced(TreeNode root) {
  return getHeight(root) >= 0;
}
private int getHeight(TreeNode root) {
  if (root == null)
    return 0;
  int leftHeight = getHeight(root.left);
  if (leftHeight < 0)
    return -1;
  int rightHeight = getHeight(root.right);
  if (rightHeight < 0)
    return -1;
  if (Math.abs(leftHeight - rightHeight) > 1)
    return -1;
  return Math.max(leftHeight, rightHeight) + 1;
}
Tags: , ,