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

   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;
	}

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;
		}
	}