[LeetCode] 114. Flatten Binary Tree to Linked List

轉自LeetCode

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

Hints:

If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.

<Solution>

這題是要把 binary tree 變成一個 flattened tree

也就是所有的 node 都是用 right node 給串起來

這邊解題想法是修改原本的 morris inorder traversal，過程如下 (參考資料)

code 如下

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	void flatten(TreeNode* root) {
	if(!root) {
	return;
	}
	TreeNode *curr = root;
	//> modified morris inorder traversal
	while(curr) {
	if(curr->left) {
	TreeNode *prv = curr->left;
	while(prv->right) {
	prv = prv->right;
	}
	prv->right = curr->right;
	curr->right = curr->left;
	curr->left = NULL;
	}
	curr = curr->right;
	}
	}
	};

view raw flattenBinaryTree_1.cpp hosted with ❤ by GitHub

再來看一個 recursive 的解法

• 先從左子樹下手，把左子樹都 flatten

• 然後 flatten 右子樹

• 合併左右子樹

• recursive 重複前面的步驟

code 如下

	/**
	* Definition for a binary tree node.
	* struct TreeNode {
	* int val;
	* TreeNode *left;
	* TreeNode *right;
	* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
	* };
	*/
	class Solution {
	public:
	void flatten(TreeNode* root) {
	if(!root) {
	return;
	}
	//> first, go to the leftest node
	if(root->left) {
	flatten(root->left);
	}
	//> second, go to the rightest node
	if(root->right) {
	flatten(root->right);
	}
	//> flatten
	TreeNode *tmpNode = root->right;
	root->right = root->left;
	root->left = NULL;
	while(root->right) {
	root = root->right;
	}
	root->right = tmpNode;
	}
	};

view raw flattenBinaryTree_2.cpp hosted with ❤ by GitHub