LeetCode:114_Flatten Binary Tree to Linked List | 将一棵二叉树变成链表的形式 | Medium

要求:Given a binary tree, flatten it to a linked list in-place.将二叉树转化为平坦序列的树。比如:

LeetCode:114_Flatten Binary Tree to Linked List | 将一棵二叉树变成链表的形式 | Medium

LeetCode:114_Flatten Binary Tree to Linked List | 将一棵二叉树变成链表的形式 | Medium

结题思路:

该题有个提示,转化后的树的序列正好是二叉树前序遍历所得到的序列,所以,该题第一个思路就是利用前序遍历的方式来做。

第二个思路:我们可以利用递归的思路,先对根节点进行处理,将root的左子树放到右子树,在将左子树中的最右端节点“嫁接”到右子树,接着上面得到的子树。接下来在用同样的方法处理当前二叉树的下一个节点。看下面一个图,即可明了。

LeetCode:114_Flatten Binary Tree to Linked List | 将一棵二叉树变成链表的形式 | MediumLeetCode:114_Flatten Binary Tree to Linked List | 将一棵二叉树变成链表的形式 | MediumLeetCode:114_Flatten Binary Tree to Linked List | 将一棵二叉树变成链表的形式 | Medium

我实现的是第二种思路,代码如下:

 struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x): val(x), left(NULL),right(NULL) {}
}; void flatten(TreeNode *root)
{
if (NULL == root)
return;
//使用stack的非递归方法
TreeNode *left = root->left;
TreeNode *right = root->right; if (left) {
root->right = left;
root->left = NULL; TreeNode *pTemp = left;
while (pTemp->right)
pTemp = pTemp->right;
pTemp->right = right; flatten(root->right);
}
}
上一篇:javascript 类型比较方法


下一篇:STS 安装SVN插件