Lexi's Leetcode solutions

Posts Tagged ‘tree

五分钟bug free,忍不住有成就感。

思路:root <= x,说明肯定不在左边,往右找;root >x,有可能是本身:如果root.left没找到,那就是本身了;如果找到了,那就返回找到那个。

public TreeNode getImmediateNext(TreeNode node, int x) {
  if (node == null)
    return null;
  if (node.val <= x) {
    return getImmediateNext(node.right, x);
  } else {
    TreeNode parent = node;
    TreeNode findAtLeft = getImmediateNext(node.left, x);
    return findAtLeft== null ? parent : findAtLeft;
  }
}
Tags: ,

这个题和前几天做的另一道“找二叉树的第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;
}

思路很straight forward,就是找到两个不属于自己位置的node,把他们的值互换。

但是怎么找这两个node就非常麻烦。怎么看出一个节点出位了?比如下图,能看出来是6出位了,但是1->6是满足的,6->3才发现不对劲。但也不能说prev > next就是prev不对,比如右边的5, 2,明明是2不对,但是2这个时候是后一个。所以总结来看,应该是“第一个不对劲的prev, curr pair是prev的错(不该跑前面的跑前面去了),第二个不对劲的prev, curr pair是curr的错(不该放后面的被放在了后面)。” 这个比较难想,总之就是中序遍历一遍,keep prev指针,按照刚说的规律找出那两个不对的。

       5
      /  \
     3     8
    / \   / \
   6   4 2   9
  /
 1

但是!!跑一遍不对!然后发现又是java不能改argument pointer的问题!栽在这上面两次了!!这回一定要弄清楚,记住教训!下面是错误版本:

private void populateMistakesArray(TreeNode[] mistakes, TreeNode root, TreeNode prev) {
  if (root == null)
    return;
  populateMistakesArray(mistakes, root.left, prev);
  if (prev != null && prev.val > root.val) {
    if (mistakes[0] == null)
      mistakes[0] = prev;
    mistakes[1] = root;
  }
  prev = root;
  populateMistakesArray(mistakes, root.right, prev);
}

这样传prev进来,prev = root这一句,method 里面叫prev的variable point to root了,然后传给下一层没问题,但是没法传给上一层!因为毕竟改的是local var, 上一层prev还是以前那个prev!!以前一直这么写树的题都没问题,是因为parameter要么一路往下传,要么想往上传的话就作为return object往上传。这次坑爹的,想往上传还放paramter里,必须挂。解决方法:用一个array把prev包起来(TreeNode[] preWrapper),就能真的改para的内容了(prevWrapper[0] = root)

keep in order traversal pointer是个固定trick,见https://leetcodenotes.wordpress.com/2013/08/28/phone-%E6%A0%91populate-%E6%AF%8F%E4%B8%AA%E8%8A%82%E7%82%B9%E7%9A%84successor-pointer/

————————————————-10月份重做——————————————————

这个题第二遍做,又栽在一个trick里——如果swap的两个数正好在中序里面连着,那只能detect出来一次Out of order(比如1235467,发现5>4,然后mistake[0]放上5了,然后4<6,正常一路下去,mistake[1]永远也没被populate出来)。为了接住这个情况,在发现mistake[0]之后立刻把下一个当作mistake[1]赋上,要是后面真有mistake[1],反正也会覆盖;要是后面没有,正好接住了上面说的特殊情况)。

Tree的test case:

 

很简单的题,因为熟悉了用两个list做tree的bfs,所以这里一层一层iterate就行了,上一层反正已经做完了,所以能直接横着遍历上一层,把下一层populate了。轻松过。

Tags: , ,

经典中的经典。

前序 pre order (中左右):

  1. push root
  2. pop,若有right, push right,若有left push left
  3. 这样继续一边pop一边push。直到stack为空。
public void preOrder(TreeNode root) {
  if (root == null)
    return;
  Stack<TreeNode> s = new Stack<TreeNode>();
  s.push(root);
  while (!s.isEmpty()) {
    TreeNode top = s.pop();
    System.out.print(top.val + ", ");
    if (top.right != null)
      s.push(top.right);
    if (top.left != null)
      s.push(top.left);
  }
}

中序 in order (左中右):

  1. push root左支到死
  2. pop, 若pop的有right,则把right当root对待push它的左支到死。
  3. 这样继续一边pop一边push。直到stack为空。
public void inOrder(TreeNode root) {
  if (root == null)
    return;
  Stack<TreeNode> s = new Stack<TreeNode>();
  pushAllTheyWayAtLeft(s, root);
  while (!s.isEmpty()) {
    TreeNode top = s.pop();
    System.out.print(top.val + ", ");
    if (top.right != null)
      pushAllTheyWayAtLeft(s, top.right);
  }
}
private void pushAllTheyWayAtLeft(Stack<TreeNode> s, TreeNode root) {
  while (root != null) {
    s.push(root);
    root = root.left;
  }
}

another way: keep a curr pointer, when curr is null means reached the left most, then start popping

    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        TreeNode curr = root;
        while (!stack.isEmpty() || curr != null) {
            if (curr != null) {
                stack.push(curr);
                curr = curr.left;
            } else {
                curr = stack.pop();
                result.add(curr.val);
                curr = curr.right;
            }
        }
        return result;
    }

想练习translate recursion to iteration,的确很难。。本来是这么想的:

stack.push(root);
while (!empty(stack)) {
   Node node = stack.pop();
   check if node is leaf, if so, compare curr sum to x, if not equals x, then currsum -= leaf.val
   else
      node.push(node.right);
      node.push(node.left);
}
   a
  / \
 b   c
/ \
d  e

然后就悲剧了。这样的话,比如上面的数,到e了,pop出e, 但是currSum只减去了e的值,b的值还留着,然后就pop c了,所以右边就永久的留下了b的值在currSum里面。怎么能知道“该pop parent”了呢?显然要一路pop出去的话,还得套个循环。另外别每次把左右两枝都push进去,一次push一个就好了。这样stack里面永远是一条valid的path。

while (!empty(stack)) {
    Node node = stack.peak();
    if (node.left exists)
       stack.push(node.left);
       currSum += node.left.val;
    } else if (node.right exists)
       do the same for right node
    } else {
       // this is a leaf now, you want to 
       1.看currSum是不是符合,不符合的话,这个leaf就得出去了
       2.看要不要把parent一起pop出去
       if (currSum == x)
          return true;
       Node child = stack.pop();
       currSum -= child.val;
       while (stack is not empty) {
         Node parent = stack.peek();
         if (child is parent's left && parent has no right || child is parent's right) {
            //说明这一支已经结束,parent也改闪了。
            stack.pop();
            currSum -= parent.val;
            child = parent;
         } else {
            //说明这一支还没结束,parent的右孩子还没处理,所以把右孩子push进去,path改了方向。
            stack.push(parent.right);
            currSum += parent.right.val;
            break;
         }
    }
}
          
          

本来觉得是弱智题,但是基本从来不top down的做树的题,写完还真挂在bug上了。

top down利用leaf的树题一般是这样的pattern:

void topDown(Node node) {
    if (node == null)
        //this means reaching a branch that only one side has something, the other side is this (null)
    if (node.left == null && root.right == null)
        //this is leaf, do something, then return;
    topDown(node.left);
    topDown(node.right);
}

和平时做的preorder(中左右)的区别:preOrder这种遍历下来,的确会在empty node的时候停,但是不能判断什么时候到了叶子节点。而topDown利用了叶子节点的定义来判断当前节点是否叶子,可以这时候做一些运算。

void preOrder(Node node) {
   if (node == null)
   //this could either mean parent is a leaf, or parent's this branch is empty but has another child
   }
   preOrder(node.left);
   preOrder(node.right);
}
Tags: , ,

尼玛这破题居然跑了好几遍才对!

一开始错的方法:

public int minDepth(TreeNode root) {
  if (root == null)
    return 0;
  int left = minDepth(root.left);
  int right = minDepth(root.right);
  return Math.min(left, right) + 1;
}

比如a#b这种左子树为空的树,我直接认为左子树的depth为0了,那当然左子树的depth小,然后parent直接取了0+1。问题在于,某个子树是null的时候,它不是叶子节点啊!这个时候就算没形成一个叶子到root的path,则认为depth为正无穷。改进:

public int minDepth(TreeNode root) {
  if (root == null)
    return Intger.MAX_VALUE;
  if (root.left == null && root.right == null)
    return 1; //说明是个leaf了!
  int left = minDepth(root.left);
  int right = minDepth(root.right);
  return Math.min(left, right) + 1;
}

忍不住回忆为啥做maxdepth的时候就没遇见问题呢?(如下)因为求的是max,所以那种某个子树为0的情况就被Math.max给解决了。总之这种题最好做完了试一试,一试就能立刻看出毛病了,自己干想还真想不到。

public int maxDepth(TreeNode root) {
  if (root == null)
    return 0;
  int left = maxDepth(root.left);
  int right = maxDepth(root.right);
  return Math.max(left, right) + 1;
}
Tags: ,

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

思路:

  1. pre的第一个肯定是root
  2. 在in里找root出现的位置m,那in的current subarray的左边就是左子树,右边就是右子树
  3. 左子树left size大小是m – a
  4. 那么pre里面root之后的left size个就是pre里面的左子树,可以将它作为一个subarray开始下一层递归了
  5. pre里面root + leftsize之后的那一半(到q为止)就是pre里面的右子树,可以将它作为一个subarray开始下一层递归,返回作为root的右子树。
  6. 所以一共三个变量:
    • p the beginning of PRE’s current subarray (subtree)
    • q the end of PRE’s current subarray (subtree)
    • a the beginning of IN’s current subarray (subtree)
private TreeNode constructFromInAndPre(int[] PRE, int[] IN, int p, int q, int a) {
  if (p > q)
    return null;
  TreeNode root = new TreeNode(PRE[p]);
  int m = findIndex(PRE[p], IN); //the index of the current root in the IN order
  if (m < 0)
    System.out.println("not exist");
  int leftSize = m - a; //the left subtree of root's size
  root.left = constructFromInAndPre(PRE, IN, p + 1, p + leftSize, a);
  root.right = constructFromInAndPre(PRE, IN, p + leftSize + 1, q, m + 1);
  return root;
}
Tags:

Blog Stats

  • 222,235 hits
September 2021
M T W T F S S
 12345
6789101112
13141516171819
20212223242526
27282930