Flatten Binary Tree to Linked List
Oct 14 '124412 / 13068
Oct 14 '124412 / 13068
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.
其实就是前序遍历,在加上个队尾指针。
/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* Tail; void preOrder(TreeNode* root) { if(root != NULL) { TreeNode* left = root->left; TreeNode* right = root->right; if(Tail == NULL){ Tail = root; } else{ if(Tail->right != root) Tail->right = root; Tail->left = NULL; Tail = root; } preOrder(left); preOrder(right); } } void flatten(TreeNode *root) { // Start typing your C/C++ solution below // DO NOT write int main() function Tail = NULL; preOrder(root); } };