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

leetcode - Flatten Binary Tree to Linked List

2024-07-08 23:30:55   223人阅读

题目：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

click to show hints.

Hints:

If you notice carefully in the flattened tree, each node‘s right child points to the next node of a pre-order traversal.

 

个人思路：

1、创建一个队列，把节点按照先序遍历的顺序入队

2、把节点挨个出队，前一个出队节点是后一个出队节点的父节点，后一个出队节点是前一个出队节点的右孩子节点，且每个非叶节点的左孩子为空

 

代码：

 1 #include <stddef.h> 2 #include <iostream> 3 #include <queue> 4  5 using namespace std; 6  7 struct TreeNode 8 { 9     int val;10     TreeNode *left;11     TreeNode *right;12     TreeNode(int x) : val(x), left(NULL), right(NULL) {}13 };14 15 class Solution16 {17 public:18     void flatten(TreeNode *root)19     {20         if (!root)21         {22             return;23         }24 25         queue<TreeNode *> preNodes;26         preorder(root, preNodes);27         root = preNodes.front();28         preNodes.pop();29         TreeNode * currentNode = root;30         while (!preNodes.empty())31         {32             TreeNode *tmp = preNodes.front();33             preNodes.pop();34             currentNode->right = tmp;35             currentNode->left = NULL;36             currentNode = currentNode->right;37         }38     }39 private:40     void preorder(TreeNode *root, queue<TreeNode *> &preNodes)41     {42         if (!root)43         {44             return;45         }46         preNodes.push(root);47         preorder(root->left, preNodes);48         preorder(root->right, preNodes);49     }50 };
View Code

 

在网上看到一个比较普遍的递归算法，链接：http://blog.unieagle.net/2012/12/16/leetcode-problemflatten-binary-tree-to-linked-list/，里面有比较详细的思路解析，可以参考，大致思路是这样：要扁平化一棵树，则扁平化根节点的左子树和右子树，然后将左子树放到根节点的右孩子位置，右子树放到左子树的叶节点的右孩子位置

 

代码：

 1 #include <stddef.h> 2 #include <iostream> 3 #include <queue> 4  5 using namespace std; 6  7 struct TreeNode 8 { 9     int val;10     TreeNode *left;11     TreeNode *right;12     TreeNode(int x) : val(x), left(NULL), right(NULL) {}13 };14 15 class Solution16 {17 public:18     void flatten(TreeNode *root)19     {20         /*21         if (!root)22         {23             return;24         }25 26         queue<TreeNode *> preNodes;27         preorder(root, preNodes);28         root = preNodes.front();29         preNodes.pop();30         TreeNode * currentNode = root;31         while (!preNodes.empty())32         {33             TreeNode *tmp = preNodes.front();34             preNodes.pop();35             currentNode->right = tmp;36             currentNode->left = NULL;37             currentNode = currentNode->right;38         }39         */40 41         if (!root)42         {43             return;44         }45         if (root->left)46         {47             flatten(root->left);48         }49         if (root->right)50         {51             flatten(root->right);52         }53         if (!root->left)54         {55             return;56         }57 58         TreeNode *left_leaf = root->left;59         while (left_leaf->right)60         {61             left_leaf = left_leaf->right;62         }63         left_leaf->right = root->right;64         root->right = root->left;65         root->left = NULL;66     }67 private:68     void preorder(TreeNode *root, queue<TreeNode *> &preNodes)69     {70         if (!root)71         {72             return;73         }74         preNodes.push(root);75         preorder(root->left, preNodes);76         preorder(root->right, preNodes);77     }78 };
View Code

 

链接中还有一个非递归的思路，大家也可以看看


联系
我们