注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex 114 Flatten Binary Tree to Linked List  

2015-05-17 19:52:46|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

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.

这个题目看起来如果不是原址遍历的话,其实还挺简单的,它的flattened过程就是先序遍历的过程,我表示这是我自己发现的。开始写的程序不是原址操作的,另外开了一个空间,导致总是过不去。后来才发现要原址操作。然后画图分析了一下,应该还是深度优先递归的过程,就是不断把左子树展开,挂到右子树上去,原来的右子树往下挪。分析见下图
ex 114 Flatten Binary Tree to Linked List - HT - HT·生活
 
c代码如下

int traverse(struct TreeNode* current, int *index, int* result, int depth)
{
if ((current->left == NULL) && (current->right == NULL))
{

return 0;
}
else
{
struct TreeNode* left = NULL, *right = NULL,*p=NULL;
if (current->left != NULL)
{
left = current->left;
traverse(current->left, index, result, depth + 1);
if (current->right != NULL)
{
current->left = NULL;

right = current->right;

current->right = left;

p = left;
//关键点在这个循环上,因为当左子树添加到右子树上的时候
//必须找到左子树的最右节点,然后最右节点链接到以前的右子树上
while (p->right != NULL)
p = p->right;


p->right = right;
traverse(right, index, result, depth + 1);
return 1;
}
//右边是空的直接把左边的接上去就行了
current->left = NULL;
current->right = left;
return 2;

}
else
{
//左子树是空,什么也不用做,直接遍历右子树即可
traverse(current->right, index, result, depth + 1);
return 3; //其实返回值没有多大用
}

}
}
void flatten(struct TreeNode* root) {
if (root == NULL)
return;
int index = 0;
int size = 10000;
int *result = (int*)malloc(size*sizeof(int));
int depth = traverse(root, &index, result, 0);
}


update java version with neat code 2015/12/4
三种递归方式本质上是一样的,但是第三种最简洁

import ht.TreeNode;
public class FlattenBinaryTreetoLinkedList {
public void flatten(TreeNode root) {
helper(root);
}
private void helper(TreeNode root) {
//TreeNode head = new TreeNode(Integer.MAX_VALUE);
//head.left = root;
//TreeNode tail = new TreeNode(Integer.MIN_VALUE);
//head = dfs(head, tail);
//root = head.right;
//TreeNode[] label = dfs2(head);
//root = head.right;
TreeNode[] tail = new TreeNode[1];
tail[0] = null;
dfs3(root, tail);
return;
}
private TreeNode dfs(TreeNode root, TreeNode tail) {
if (root.right == null && root.left == null) {
tail.right = root;
return root;
} else {
if (root.left == null || root.right == null) {
root.left = root.right == null ? root.left : root.right;
TreeNode head = dfs(root.left, tail);
root.right = head;
root.left = null;
return root;
} else {
TreeNode current = root.right;
TreeNode head = dfs(root.left, tail);
root.right = head;
root.left = null;

TreeNode tmpTail = new TreeNode(Integer.MIN_VALUE);
head = dfs(current, tmpTail);
tail.right.right = head;
tail.right = tmpTail.right;
return root;
}
}
}
private TreeNode[] dfs2(TreeNode root) {
// 每次递归返回首尾节点
if (root.right == null && root.left == null) {
TreeNode[] label = {root, root};
return label;
} else {
if (root.left == null || root.right == null) {
root.left = root.right == null ? root.left : root.right;
TreeNode[] leftLabel = dfs2(root.left);
root.right = leftLabel[0];
root.left = null;
leftLabel[0] = root;
return leftLabel;
} else {
TreeNode current = root.right;
TreeNode[] leftLabel = dfs2(root.left);
root.right = leftLabel[0];
root.left = null;

TreeNode[] rightLabel = dfs2(current);
leftLabel[1].right = rightLabel[0];
rightLabel[0] = root;
return rightLabel;
}
}
}
private TreeNode dfs3(TreeNode root, TreeNode[] tail) {
// 这个递归是最简洁的
if (root == null) {
return tail[0];
}
TreeNode[] head = new TreeNode[1];
head[0] = dfs3(root.right, tail);
root.right = dfs3(root.left, head);
root.left = null;
return root;
}
}


  评论这张
 
阅读(4)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017