一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 1213|回复: 8
收起左侧

[Leetcode] 问一道LeetCode简单题

[复制链接] |试试Instant~ |关注本帖
tacit 发表于 2014-3-16 21:34:54 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
Flatten Binary Tree to Linked List: http://oj.leetcode.com/problems/ ... ree-to-linked-list/
题目说了要in-place, 但lz最初还是写了一个非in-place的。但一直没法过。好奇背后的test是怎么run的,求指点!
  1. public class Solution {
  2.         private void preOrder(TreeNode root, TreeNode tmp) {
  3.         tmp.right = new TreeNode(root.val);
  4.         if (root.left != null) {
  5.             preOrder(root.left, tmp.right);
  6.         }
  7.         if (root.right != null) {
  8.             preOrder(root.right, tmp.right);
  9.         }
  10.     }
  11.    
  12.     public void flatten(TreeNode root) {
  13.         if (root == null) {
  14.             return;
  15.         }
  16.         
  17.         TreeNode tmp = new TreeNode(0);
  18.         
  19.         preOrder(root, tmp);
  20.         root = tmp.right;
  21.     }
  22. }
复制代码
海地民工 发表于 2014-3-17 04:26:48 | 显示全部楼层
我是小白~说一下我的方法吧:
从一个根节点开始找左子树的最右节点,然后将根节点的右子树作为这个最右节点的有孩子,然后再将跟的整个左子树放到跟的右边,左子树设为null, 说白了就是切断根和右子树的联系,把左子树整个塞进去,然后递归就好了。
  1. public void flatten(TreeNode root) {
  2.         if(root == null) return;
  3.         if(root.left == null && root.right == null) return;
  4.         if(root.left == null)
  5.         {
  6.             flatten(root.right);
  7.             return;
  8.         }
  9.         TreeNode p = root.left;
  10.         while(p.right != null) p = p.right;
  11.         p.right = root.right;
  12.         root.right = root.left;
  13.         root.left = null;
  14.         flatten(root.right);
  15.         
  16.     }
复制代码
回复 支持 反对

使用道具 举报

 楼主| tacit 发表于 2014-3-17 09:48:28 | 显示全部楼层
本帖最后由 tacit 于 2014-3-17 10:03 编辑

谢谢!这样是可以。

但我就想另外建一棵树,然后前序遍历原来的树,分别把节点都复制到新树的右节点,最后把原树的根指向新树,不知这样为啥不可以。
回复 支持 反对

使用道具 举报

海地民工 发表于 2014-3-17 10:11:58 | 显示全部楼层
tacit 发表于 2014-3-17 09:48
谢谢!这样是可以。

但我就想另外建一棵树,然后前序遍历原来的树,分别把节点都复制到新树的右节点, ...

我估计oj在检测的时候不是检测节点中的值对不对,而是看你有没有把已经存在的节点放到他应该的位置,你新建的对象肯定不是原来的了,所以过不了,我也是猜的~
回复 支持 反对

使用道具 举报

 楼主| tacit 发表于 2014-3-17 10:34:37 | 显示全部楼层
海地民工 发表于 2014-3-17 10:11
我估计oj在检测的时候不是检测节点中的值对不对,而是看你有没有把已经存在的节点放到他应该的位置,你新 ...

谢谢!有道理。题目也明确说了in-place.
回复 支持 反对

使用道具 举报

sjtuzyt 发表于 2014-3-18 09:54:27 | 显示全部楼层
  1. class Solution {
  2. public:
  3.     void flatten(TreeNode *root) {
  4.         if(!root) return;
  5.         flatten(root->left);
  6.         flatten(root->right);
  7.         TreeNode* tmp=root->right;
  8.         if(root->left){
  9.             root->right=root->left;
  10.             root->left=NULL;
  11.             while(root->right)
  12.                 root=root->right;
  13.             root->right=tmp;
  14.         }
  15.     }
  16. };
复制代码
这个题的评测有点问题, root->left=NULL;这一行如果放在root->right=tmp;之后,跑{1,#,2}就会有run time error,但是在vs2010,codeblocks里跑都没问题。调整成上面代码那样就可以评测通过了。
回复 支持 反对

使用道具 举报

shiningsnow 发表于 2014-3-18 13:08:56 | 显示全部楼层
我的代码
// left as last, right as next
BinaryTreeNode* subTree2LinkList(BinaryTreeNode* node, BinaryTreeNode* prior,
                BinaryTreeNode* last) {

        BinaryTreeNode* head;

        if (node->left != NULL) {
                head = subTree2LinkList(node->left, prior, node);
        } else {
                if (prior == NULL) {
                        head = node;
                } else {
                        node->left = prior;
                        prior->right = node;
                }
        }
        if (node->right != NULL) {
                subTree2LinkList(node->right, node, last);
        } else {
                if (last != NULL) {
                        node->right = last;
                        last->left = node;
                }
        }

        if (prior == NULL)
                return head;
        else
                return NULL;

}

BinaryTreeNode* binaryTree2DoubleDirectionLinklist(BinaryTreeNode* root) {

        BinaryTreeNode* headNode;

        if (root->left == NULL) {
                headNode = root;
        } else {
                headNode = subTree2LinkList(root->left, NULL, root);
        }

        if (root->right != NULL) {
                subTree2LinkList(root->right, root, NULL);
        }
        return headNode;

}
回复 支持 反对

使用道具 举报

landuostorm 发表于 2014-3-21 00:11:36 | 显示全部楼层
来一发喜闻乐见的iterative吧
  1. class Solution {
  2. public:
  3.     void flatten(TreeNode *root) {
  4.        if (root == nullptr) return;
  5.        stack<TreeNode*> s;
  6.        s.push(root);
  7.         
  8.         while(!s.empty()) {
  9.             auto p = s.top();
  10.             s.pop();
  11.             if(p -> right)
  12.                 s.push(p -> right);
  13.             if(p -> left)
  14.                 s.push(p -> left);
  15.             p -> left = nullptr;
  16.             if(!s.empty())
  17.                 p -> right = s.top();
  18.         }
  19.     }
  20. };
复制代码
回复 支持 反对

使用道具 举报

anikin0617 发表于 2014-3-30 01:58:55 | 显示全部楼层
海地民工 发表于 2014-3-17 04:26
我是小白~说一下我的方法吧:
从一个根节点开始找左子树的最右节点,然后将根节点的右子树作为这个最右节 ...

你这个挺巧妙的,就是不太好想到啊,是不是用一个Stack做辅助的话更直观呢。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 08:28

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表