问一道LeetCode简单题

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. }

复制代码

我是小白～说一下我的方法吧：
从一个根节点开始找左子树的最右节点，然后将根节点的右子树作为这个最右节点的有孩子，然后再将跟的整个左子树放到跟的右边，左子树设为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.     }

复制代码

海地民工 发表于 2014-3-17 04:26
我是小白～说一下我的方法吧：
从一个根节点开始找左子树的最右节点，然后将根节点的右子树作为这个最右节 ...

谢谢！这样是可以。

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

tacit 发表于 2014-3-17 09:48
谢谢！这样是可以。

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

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

海地民工 发表于 2014-3-17 10:11
我估计oj在检测的时候不是检测节点中的值对不对，而是看你有没有把已经存在的节点放到他应该的位置，你新 ...

谢谢！有道理。题目也明确说了in-place.

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里跑都没问题。调整成上面代码那样就可以评测通过了。

我的代码
// 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;

}

来一发喜闻乐见的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. };

复制代码

海地民工 发表于 2014-3-17 04:26
我是小白～说一下我的方法吧：
从一个根节点开始找左子树的最右节点，然后将根节点的右子树作为这个最右节 ...

你这个挺巧妙的，就是不太好想到啊，是不是用一个Stack做辅助的话更直观呢。