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

Flatten Binary Tree to Linked List

2024-07-17 23:18:16   222人阅读

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

思路：该题本质上是二叉树的先序遍历。我们首先来看递归的解法，函数FlattenSub(node)对以node为根的树进行处理，同时返回先序序列的尾节点的指针：

 1 class Solution { 2 public: 3     void flatten( TreeNode *root ) { 4         if( !root ) { return; } 5         FlattenSub( root ); 6     } 7 private: 8     TreeNode *FlattenSub( TreeNode *node ) { 9         if( node->left ) {10             TreeNode *left_last = FlattenSub( node->left );11             left_last->right = node->right;12             node->right = node->left;13             node->left = 0;14             return FlattenSub( left_last );15         }16         if( node->right ) { return FlattenSub( node->right ); }17         return node;18     }19 };

接下来再看迭代的解法，基本思想是将父节点的地址保存到其左子树最右侧节点（即先序遍历的尾节点）的右指针字段，这样在左子树处理完成之后，可以再次回到父节点以完成对右子树的处理。

 1 class Solution { 2 public: 3     void flatten( TreeNode *root ) { 4         if( !root ) { return; } 5         while( root ) { 6             if( root->left ) { 7                 TreeNode *node = root->left; 8                 while( node->right && node->right != root ) { node = node->right; } 9                 if( node->right == root ) {10                     node->right = root->right;11                     root->right = root->left;12                     root->left = 0;13                 } else {14                     node->right = root;15                     root = root->left;16                 }17             }18             TreeNode *node = root;19             while( node->right && !node->right->left ) { node = node->right; }20             if( node->right && node->right->left == root ) {21                 root = node->right;22                 node->right = root->right;23                 root->right = root->left;24                 root->left = 0;25             } else {26                 root = node->right;27             }28         }29         return;30     }31 };

 


联系
我们