Author: Minghua Tong

You don’t know i++

b的值时2还是3？ i++要这样理解：先把当前的i保存下来，作为parameter，但不立刻执行其传入的expression。此时，执行i = i + 1，然后再执行expression。 对于b = a++ + a++;首先将a = 1代入第一个a：b = 1 + a++;注意，此时表达式并不立刻继续执行，而是先执行a = a+ 1。此时a=2，带入第二个a：b = 1 + 2;因此结果是3。 return value++;这会先把value返回，然后立刻执行value =… Read more “You don’t know i++”

by Minghua Tong

Binary Search的临界点分析

Binary Search说来容易，但容易出错，原因在于临界点选择。而需要考虑临界点的位置竟然有3处之多，且彼此联系。 首先，有两个原则： The target cannot be ruled out. The search space decreases over time. 最基本的Binary Search: Critical Point 1: loop终止条件 跳出loop时，left > right。通常用在target是一个确定值，而不是一个不确定的概念（比如最接近某值）时。所谓确定，就是说loop中找到符合条件的元素时就可以直接return。loop结束时就说明target没找到，因此不需要post processing。 结束时left ==… Read more “Binary Search的临界点分析”

by Minghua Tong

Time Complexity of Recursion Trees with O(1) for Each Node

对于n叉recursion tree，不管是BFS1或者DFS，如果每次recursion的time complexity都是O(1)，那么总的time complexity就转化成了计算node的总数。 对于二叉树，各层的节点数量依次为(n层)：1, 2, 4, …, 2^(n-2), 2^(n-1)。总数可以这样计算：1 + 2 + 4 + … + 2^(n-2) + 2^(n-1)= 2^n(1/(2^n) + 1/(2^(n-1)) + … + 1/4… Read more “Time Complexity of Recursion Trees with O(1) for Each Node”

by Minghua Tong

Thoughts on Binary Tree Iterative Traversal

Iterative Traversal本质是把稍后要处理的Node放到stack上，然后依逻辑不断地pop和push，直到stack为空。每次iteration，都从stack上pop出一个node，然后根据其状态采取不同的处理。理论上，每次对node的访问，可以有三种状态：from parent node, from left child and from right child。再往深入想，状态的数量其实是由print的顺序决定的。Node之所以被放入stack，是因为要在将来某时刻print，换句话说，一旦该node完成了print，它就不会再次被访问。 Pre-Order Traversal 第一次访问node，就立刻print，此后不会有第二次访问该node的可能性。所以对于pre-order，pop出来的node只有一种状态，不需要额外的flag来指示状态。 In-Order Traversal Node在第二次访问时才会被打印，因此有两个状态：from parent node and from left child。所以，用一个boolean就可以区分两种状态。需要注意的是第二次访问时才从stack中pop，所以在进入循环时选择peek。 老师给的解法其实很有技巧性。helper为null时表示从from left child，反之则表示from parent… Read more “Thoughts on Binary Tree Iterative Traversal”

by Minghua Tong