| * | |
| * 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) {} | |
| * }; | |
新生成的List的每个节点的右子树指向的是 先序遍历中该节点的下一个节点。那么本题其实就是考察先序遍历。
class Solution {
public:
void flatten(TreeNode *root) {
vector<TreeNode*> v, stack;
stack.push_back(root);
while(stack.size()>0){
TreeNode* node = stack.back();
stack.pop_back();
v.push_back(node);
if (node && node->right){
stack.push_back(node->right);//先入栈右子树，后出栈右子树
}
if (node && node->left){
stack.push_back(node->left);//后入栈左子树，先出栈左子树
}
}
v.push_back(NULL);
for(int i=0; i<v.size(); i++){//按照先序遍历的顺序将节点链接起来
if (v[i]){
v[i]->left = NULL;
v[i]->right = v[i+1];
}
}
}
};
版权声明：本文为博主原创文章，未经博主允许不得转载。
Flatten Binary Tree to Linked List
原文：http://blog.csdn.net/ruzhuxiaogu/article/details/47379635