首页 > 代码库 > LeetCode:Flatten Binary Tree to Linked List
LeetCode:Flatten Binary Tree to Linked List
要求:Given a binary tree, flatten it to a linked list in-place.将二叉树转化为平坦序列的树。比如:
结题思路:
该题有个提示,转化后的树的序列正好是二叉树前序遍历所得到的序列,所以,该题第一个思路就是利用前序遍历的方式来做。
第二个思路:我们可以利用递归的思路,先对根节点进行处理,将root的左子树放到右子树,在将左子树中的最右端节点“嫁接”到右子树,接着上面得到的子树。接下来在用同样的方法处理当前二叉树的下一个节点。看下面一个图,即可明了。
我实现的是第二种思路,代码如下:
1 struct TreeNode { 2 int val; 3 TreeNode* left; 4 TreeNode* right; 5 TreeNode(int x): val(x), left(NULL),right(NULL) {} 6 }; 7 8 void flatten(TreeNode *root) 9 {10 if (NULL == root)11 return;12 //使用stack的非递归方法13 TreeNode *left = root->left;14 TreeNode *right = root->right;15 16 if (left) {17 root->right = left;18 root->left = NULL;19 20 TreeNode *pTemp = left;21 while (pTemp->right)22 pTemp = pTemp->right;23 pTemp->right = right;24 25 flatten(root->right);26 }27 }
LeetCode:Flatten Binary Tree to Linked List
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。