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
1 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */ 10 class Solution { 11 public: 12 void flatten(TreeNode *root) { 13 if (root == nullptr) { 14 return; 15 } 16 if (root->left != nullptr) { 17 flatten(root->left); 18 } 19 if (root->right != nullptr) { 20 flatten(root->right); 21 } 22 if (root->left != nullptr) { 23 TreeNode *tail = root->left; 24 while (tail->right != nullptr) { 25 tail = tail->right; 26 } 27 tail->right = root->right; 28 root->right = root->left; 29 root->left = nullptr; 30 } 31 } 32 };
flatten后的链表顺序与树的先序遍历一致。树的问题通常可以考虑递归。
也可以借助栈迭代求解:
1 /** 2 * Definition for binary tree 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */ 10 class Solution { 11 public: 12 void flatten(TreeNode *root) { 13 if(root == nullptr) { 14 return; 15 } 16 stack<TreeNode *> s; 17 s.push(root); 18 while (!s.empty()) { 19 TreeNode *p = s.top(); 20 s.pop(); 21 if (p->right != nullptr) { 22 s.push(p->right); 23 } 24 if (p->left != nullptr) { 25 s.push(p->left); 26 } 27 if (!s.empty()) { 28 p->right = s.top(); 29 } 30 p->left = nullptr; 31 } 32 } 33 };