Leetcode Flatten Binary Tree to Linked List

Flatten Binary Tree to Linked List

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.

深入理解了指针和树的操作，那么这道题是十分简单的，但是没理解好，那么这道题是非常难的。

重要一点：遍历访问的时候，不能改变没有访问过的树节点的结构。

也因为这一点，所以这道题不能像普通先序遍历那样写程序。

仔细观察思考会发现两点特征：

1 修改后的树只有右子树，

2 访问过之后的节点是可以修改其结构的

那么我们可以使用逆先序遍历 - 因为先访问最右边的右子树，那么这个右子树不会在后面的访问中需要了，就可以改变其树形结构了。

想清楚这一点之后，这道题就变得非常简单了。

下面两个逆先序遍历的程序都十分简单：

1.

void flatten(TreeNode *root) 
	{
		if (!root) return;
		TreeNode *dummy = new TreeNode(-1);
		flatten(root, dummy);
		//root = dummy->right;可以不用这句
		delete dummy;
	}
	void flatten(TreeNode *root, TreeNode *(&res)) 
	{
		if (!root) return;
		flatten(root->right, res);
		flatten(root->left,res);
		root->right = res->right;
		res->right = root;
		root->left = nullptr;
	}

2.

void flatten2(TreeNode *root) 
	{
		if (!root) return;
		flatten2(root->right);
		flatten2(root->left);
		if (root->left)
		{
			TreeNode *rMost = root->left;
			while (rMost->right) rMost = rMost->right;
			rMost->right = root->right;
			root->right = root->left;
			root->left = nullptr;
		}
	}

//2014-2-17 update
	void flatten(TreeNode *root) 
	{
		if (!root) return;
		flatten(root->right);
		flatten(root->left);
		
		if (root->left)
		{
			TreeNode *p = root->left;
			while (p->right) p = p->right;
			p->right = root->right;
			root->right = root->left;
			root->left = nullptr;
		}
	}