Tree的总结

  1. 树的遍历

树的三种遍历: pre-order, in-order, post-order 遍历方法:
1. recursive的方法,递归条件的选择
2. iterative的方法, 用stack来实现, 需要一个current指向root的当前节点,注意判断current是否为空,跟stack是否为空都是很重要的条件。

前序遍历(pre-order): 根->左->右
Iterative: 1. 对root异常处理 2.cur 指向root, 循环条件为cur!=null || !stack.isEmpty() 3.当cur不为空,就压入stack,并将元素加入结果,cur继续往左边找 4.当cur为空,就cur就为pop出的栈顶元素,.cur继续往右边找. 5.返回最终结果集合.

中序遍历(in-order):左->根->右
Iterative: 1. 对root异常处理 2.cur指向root, 循环条件为cur!=null||!stack.isEmpty()
3.当cur不为空,就压入stack, cur继续往左边找 4.当cur为空,就cur就为pop出的栈顶元素,并将元素加入结果,cur继续往右边找. 5.返回最终结果集合.

后序遍历(post-order): 左 ->右->根
Iterative: 1. 对root异常处理 2.cur指向root, 循环条件为cur!=null||!stack.isEmpty()
3.当cur不为空,将cur放到栈,继续往右边寻找 4. 当cur为空,pop出栈顶元素,并加到result里面,cur继续往左边寻找 5. 最好返回Collection.reverse(result)

以为三种遍历方法的recursive解法都很相似, 都可以用divide&conquer的方法来做。 1.每次初始个result的list2. 检查root是否为空,空的话返回当前结果集合 3.(divide) 求左子树的集合序列,求右子树的集合序列。 4. (Conquer)这里根据不同的遍历方法,放入集合的顺序也不同. pre-order: 先放跟节点值,再左子树集合,再右子树集合; in-order: 先放左子树集合,再放根节点,再放右子树集合; post-order:先放左子树集合,再放右子树集合,最后放根节点的值。5. 返回最终结果集合.

应用: BST Iterator
思路: 可以用中序遍历(in-order)来做, 利用一个current节点跟stack来模拟中序遍历,
hasNext(): cur!=null || !stack.isEmpty();
int next():
while(cur!= null) {
stack.push(cur);
cur = cur.left;
}
TreeNode node = stack.pop();
cur = node.right;
return node.val;
Serialize and Deserialize Binary Tree: 用in-order traversal的思路来做,先定义好EmptyNode跟delimiter的值。
Level-order traversal(层遍历): 用Queue来实现, 大概思路就是1. 把跟节点放入queue 2.循环条件为queue中元素不为空3. 记录先当前层的count = queue.size(),实例化个list用来存放当前层结果,然后用for循环对queue中元素遍历,挨个poll出来,把当前层结果放入list,并检查是否有left,right 节点,有的话放入queue中。 最后把当前层结果list放入最终结果当中。

应用: Binary Right Side View: 找每层最后一个节点。

Zigzag level-order traversal: 用level-order的traversal的思路,加一个标志位LR,来控制把每层遍历的元素按照从左到右还是从右到左的顺序放到最终集合res中。

  1. Validate Tree

    Validate Same Tree: 传入t1, t3 判断两个树是否是same tree。1.可以先判断都为空的情况. 2.其中一个为空的情况 3. 都不为空,但值相等情况 4. 再递归去找去找左子树 && 右子树
    Validate Symmetric Tree: 比较一棵树的左子树跟右子树是否相同,可以拆分写一个helper(t1, t2)函数,传入左子树跟右子树进行比较, 转换为Validate Same Tree的思路。
    Validate BST: 查一个树是否是BST, 看左子树的上限(upper)为根节点值,右子树下限(lower)为根节点值. 这里我们借助一个helper函数传入其上下限。 在helper函数: 1. 为null,返回true 2. 当前节点值= upper,返回false 3. 递归去判断左子树&&右子树; 注意这里要用long类型。
    Validate Balanced Binary Tree: 看树是否是balanced,看左右子树的最大深度相差不超过1。 这里我们需要借助一个depth(node)函数去求得左右子树的深度(深度选择左子树跟右子树深度的最大值),然后递归的条件就是 abs(depth(root.left) – depth(root.right)<=1) && isBalance(root.left) && isBalance(root.right);

Tree Depth

Max Depth(Tree Depth): 递归找到左子树的depth跟右子树depth中的最大的+1; 也可以用level-order traversal的思想来做.
Min Depth(从root到left的最短深度): 1. root为空,返回0 2. 求得leftDepth, rightDepth 3. leftDepth为0,返回rightDepth+1;rightDepth为0,返回leftDepth+1;都不为0的情况则返回min(leftDepth, rightDepth) + 1

  1. Tree Path Sum问题

Path Sum: 找到从root到leaf的节点之和等于给定值,我们可以用target对每个节点做减法,成立的条件为(root.left==null&&root.right==null&&root.val==sum), 然后递归分别去找左子树或右子树中可能的解。
Path Sum II: 这里要找所有解空间集合,我们可以用backtracking方法来做,思路跟Path Sum类似,不过我们需要借助个临时list,跟最终集合res, 当满足接空间集合的时候,res.add(new ArrayList(list)); 然后再去除list的最后一个元素; 当走到底的时候,没有满足的解空间,我们也要去除list最后一个元素,继续往下寻找。
Sum of Leaf Leaves: 求所有左叶子节点的和,我们需要判断该节点是否是叶子节点,如果是就加和。判断left leaf的要求就是: parent.left = cur&&cur.left==null&&cur.right==null; 这里我们可以用in-order traversal的方法去记录parent,在cur入栈之前先判断parent.left!=null, 则parent=cur; 等到pop的时候,我们就去查left node的条件就可以加入sum。
Sum Root to Leaf Numbers : 找从root到leaf构成的多位数的和;root节点的值是最高位;我们可以借助一个helper(root,preSum), 那么curSum=preSum*10+root.val, 递归停止条件为走到底,返回curSum就行,然后依次去寻找 左子树+右子树的和。
Binary Tree Path: 打印从root到leaf的所有path; 借助helper(root,path,res)函数, 递归去找左子树中path跟右子树中path,走到底就把path加到res;
5.

Common Ancestor(公共祖先问题)

LCA: 可以用divide&conquer来解,通过树的遍历,p1, p2的公共祖先必然是 1) p1或者p2中的一个; 2) p1和p2是其所在的左右子树.
复杂度: time O(n), space O(1)
1.边界检查当root==null,返回root 2.如果给定p,q中有一个为root时候,返回root. 3.给定p,q都不为root情况下,我们分别去找左子树跟右子树的LCA,left跟right,如果找到的left!=null&&right!=null,那么我们就返回root;如果有一个为null,那么我们就返回另一个为其LCA.
Follow up:
1. 对于二叉树中任意给定两点的公共祖先? 如果给出每个节点的parent,跟不给parent都有什么解法? 时间复杂度?
给定parent: 我们可以先求出给定两个点p,q分别到root的距离,并得到两个距离的差值d. 我们先让距离较长的点p往上走d步后,然后p跟q同时再往上走,直到他们第一次相遇,此点就是他们的最近公共祖先。 时间复杂度为O(n),空间为O(1)
不给定parent,就只能用树的遍历来做.
2. 对于二叉树中任意给定两点的公共祖先?如果进行多次查询该怎么做?时间复杂度?
可以加Cache,缓存每次的结果. 每次查询一组数据的平均时间复杂度:O(1)k/N^2 + O(n)(n^2-k)/n^2, k为缓存的数据

  1. Construct Tree

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s