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

click to show hints.

» 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.

	/**
	* Definition for binary tree
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	void build(TreeNode *root, TreeNode *&tmp)
	{
	if(root)
	{
	build(root->right, tmp);
	build(root->left, tmp);
	root->right=tmp;
	tmp=root;
	root->left=NULL;
	}
	}
	void flatten(TreeNode *root) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function
	TreeNode *tmp=NULL;
	build(root, tmp);
	}
	};

view raw flatten binary tree to linked list hosted with ❤ by GitHub