首页 > 代码库 > Flatten Binary Tree to Linked List <leetcode>

Flatten Binary Tree to Linked List <leetcode>

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

算法:该题用的是递归,只要考虑当前节点,思路如下,设当前节点为root,把root的左节点的最右节点的右子树指向root的右子树,然后把root的右指针指向root的左子树,root的做指针置空,下一个节点处理root->right,代码如下:

 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(NULL==root)  return;14         if(NULL!=root->left)15         {16             getLeftRight(root)->right=root->right;17             root->right=root->left;18             root->left=NULL;19         }20         flatten(root->right);21         22     }23     24     TreeNode* getLeftRight(TreeNode* root)25     {26         root=root->left;27         while(NULL!=root->right)  root=root->right;28         return root;29     }30 };

 

Flatten Binary Tree to Linked List <leetcode>