Flatten Binary Tree to Linked List

Flatten Binary Tree to Linked List

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 解析:

变换后的链表是按照先序遍历的顺序，只需要把左子树变成链表，然后链表的最后节点指向右子树的链表，把根节点右子树指向左子树链表，左子树置空即可。

代码：

/** * 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 flat(TreeNode* root) { if (root==NULL) return ; if (root->left==NULL &&root->right==NULL) return ; TreeNode *leftroot=root->left; TreeNode *rightroot=root->right; if (root->left) { flat(leftroot); } if (root->right) { flat(rightroot); } if (leftroot!=NULL) { TreeNode* temp=leftroot; while(leftroot->right) { leftroot=leftroot->right; } leftroot->right=rightroot; root->right=temp; root->left=NULL; } return ; } void flatten(TreeNode* root) { flat(root); return ; } };