Monday, July 22, 2013

Flatten binary tree to linked list@leetcode

刷题必备书籍Cracking the Coding Interview: 150 Programming Questions and Solutions 

简历:The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
算法学习书籍:Introduction to Algorithms
编程珠玑:Programming Pearls (2nd Edition)
C++ 学习:The C++ Programming Language, 4th Edition
经典操作系统书籍,龙书:Operating System Concepts
创业:The Start-up of You: Adapt to the Future, Invest in Yourself, and Transform Your Career
Given a binary tree, flatten it to a linked list in-place.
For example,
Given
         1
        / \
       2   5
      / \   \
     3   4   6
The flattened tree should look like:
   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6
» Solve this problem

这道题思路很清晰,就是递归,然后分别flat右和左,刚开始以为flat哪个先都无所谓,但实际是要先flatten右边的,不然flatten完左边,把左边的连上右边去,右边的已经不是bst了。这是第一点。

第二点,难点,也是我卡住的地方,就是如何把点连接起来。我的思路会,但就是连点连错了,导致出不来。之前我写的是

build(root->right);
build(root->left);

root->right->left=root->right;
root->right=root->left;

这样看上去是对的,但是对于完成了一颗子树,换到另一颗子树的连接就出了问题。这个时候我们要用一个treenode来保存之前跑过的node的root,以便下一次连接,于是就有了下面的代码,多了一个tmp.

No comments:

Post a Comment

Leetcode 316. Remove Duplicate Letters

 这道题表面问的是如何删除重复,实际在问如何从多个字符选取一个保留,从而让整个字符串按升序排列。那么策略就是对于高顺位的字符比如‘a',就要选靠前位置的保留,而低顺位字符如’z'则应该尽量选取靠后位置保留。 算法大概思路:每看到一个字符,我们要决定是否保留 1. ...