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: void flatten(TreeNode *root) { if(root==NULL) return; TreeNode *p = root; Recur(p); } private: void Recur(TreeNode *p){ if(p==NULL) return; TreeNode *pleft=p->left; TreeNode *pright = p->right; p->left = NULL; p->right = pleft; Recur(pleft); while(pleft){//找到pleft的最末点 p = pleft; pleft = pleft->right; } p->right = pright; Recur(pright); } };
[LeetCode] Flatten Binary Tree to Linked List,布布扣,bubuko.com
[LeetCode] Flatten Binary Tree to Linked List
原文：http://www.cnblogs.com/Xylophone/p/3890185.html