这不是一个Leetcode 题目.我自己写了下。题意如下:Convert a binary search
tree to a sorted, circular, doubly-linked list, in place (using the tree
nodes as the new list nodes).

题目

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

金沙国际官网 1Paste_Image.png

Given a binary tree, flatten it to a linked list in-place.

Given a binary tree, flatten it to a linked list in-place.

use leftChild as “prev”

解题之法

// Recursion
class Solution {
public:
    void flatten(TreeNode *root) {
        if (!root) return;
        if (root->left) flatten(root->left);
        if (root->right) flatten(root->right);
        TreeNode *tmp = root->right;
        root->right = root->left;
        root->left = NULL;
        while (root->right) root = root->right;
        root->right = tmp;
    }
};

My code:

For example,
Given
1
/
2 5
/ \
3 4 6
The flattened tree should look like:
1

For example,Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:
   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

use rightChild as “next

分析

这道题要求把二叉树展开成链表,根据展开后形成的链表的顺序分析出是使用先序遍历,那么只要是数的遍历就有递归和非递归的两种方法来求解,这里我们也用两种方法来求解。首先来看递归版本的,思路是先利用DFS的思路找到最左子节点,然后回到其父节点,把其父节点和右子节点断开,将原左子结点连上父节点的右子节点上,然后再把原右子节点连到新右子节点的右子节点上,然后再回到上一父节点做相同操作。

例如,对于下面的二叉树,上述算法的变换的过程如下:

      1
     / \
    2   5
   / \   \
  3   4   6

1
/ \
2   5
\   \
 3   6
  \    
   4

1
\
 2
  \
   3
    \
     4
      \
       5
        \
         6

下面我们再来看非迭代版本的实现,这个方法是从根节点开始出发,先检测其左子结点是否存在,如存在则将根节点和其右子节点断开,将左子结点及其后面所有结构一起连到原右子节点的位置,把原右子节点连到原左子结点最后面的右子节点之后。

// Non-recursion
class Solution {
public:
    void flatten(TreeNode *root) {
        TreeNode *cur = root;
        while (cur) {
            if (cur->left) {
                TreeNode *p = cur->left;
                while (p->right) p = p->right;
                p->right = cur->right;
                cur->right = cur->left;
                cur->left = NULL;
            }
            cur = cur->right;
        }
    }
};

例如,对于下面的二叉树,上述算法的变换的过程如下:
1
/
2 5
/ \
3 4 6

1
\
 2
/ \
3   4
    \
     5
      \
       6

1
\
 2
  \
   3
    \
     4
      \
       5
        \
         6
import java.util.ArrayList;/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode { val = x; } * } */public class Solution { public void flatten(TreeNode root) { if (root == null) return; ArrayList<Integer> nodeSet = new ArrayList<Integer>(); flatten(nodeSet, root); TreeNode newRoot = root; for (int i = 1; i < nodeSet.size { newRoot.left = null; newRoot.right = new TreeNode(nodeSet.get; newRoot = newRoot.right; } } private void flatten(ArrayList<Integer> nodeSet, TreeNode root) { nodeSet.add; if (root.left != null) flatten(nodeSet, root.left); if (root.right != null) flatten(nodeSet, root.right); } public static void main(String[] args) { TreeNode n1 = new TreeNode; TreeNode n2 = new TreeNode; TreeNode n3 = new TreeNode; TreeNode n4 = new TreeNode; TreeNode n5 = new TreeNode; n1.left = n2; n2.left = n3; n2.right = n4; n3.left = n5; Solution test = new Solution(); test.flatten; }}

2

Hints:
If you notice carefully in the flattened tree, each node’s right child
points to the next node of a pre-order traversal.

My code:

My test result:

3

分析

将二叉树转化为前序遍历的链表。使用递归,先处理左子树,然后找到左子树形成的链表的尾端,链接到右子树上,再处理右子树即可。C代码如下已通过。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
struct TreeNode* preOrder(struct TreeNode* root)
{
    if(root==NULL||(root->left==NULL&&root->right==NULL))
        return root;
    struct TreeNode *l=root->left,*r=root->right,*temp;
    root->left=NULL;
    if(l!=NULL)
    {
        printf("%d ",l->val);
        temp=preOrder(l);
        root->right=temp;
        while(temp->right!=NULL)
            temp=temp->right;
    }
    else
    {
        temp=root;
    }
    temp->right=preOrder(r);
    temp->left=NULL;
    return root;
}
void flatten(struct TreeNode* root) {
    preOrder(root);
}
import java.util.Comparator;import java.util.PriorityQueue;public class Solution { public TreeNode traverse(TreeNode root) { if (root == null) return null; return dfs[0]; } private TreeNode[] dfs(TreeNode root) { if (root == null) return null; TreeNode[] left = dfs(root.left); TreeNode head = null; TreeNode tail = null; if (left != null) { head = left[0]; left[1].right = root; root.left = left[1]; } TreeNode[] right = dfs(root.right); if (right != null) { root.right = right[0]; right[0].left = root; tail = right[1]; } TreeNode[] ret = new TreeNode[2]; ret[0] = (head == null ? root : head); ret[1] = (tail == null ? root : tail); return ret; } public static void main(String[] args) { Solution test = new Solution(); TreeNode a1 = new TreeNode; TreeNode a2 = new TreeNode; TreeNode a3 = new TreeNode; TreeNode a4 = new TreeNode; TreeNode a5 = new TreeNode; TreeNode a6 = new TreeNode; TreeNode a7 = new TreeNode; a1.left = a2; a1.right = a3; a2.left = a4; a2.right = a5; a3.left = a6; a3.right = a7; TreeNode head = test.traverse; TreeNode tail = null; while (head.right != null) { System.out.println; head = head.right; } System.out.println; tail = head; System.out.println("**************"); while (tail != null) { System.out.println; tail = tail.left; } }}

金沙国际官网 2Paste_Image.png

4

自己测试了下。感觉差不多了。其实就是一个简单的dfs,in order traverse
this tree.然后每次返回一个数组,第一位放head of sub tree, 第二位放tail
of sub tree然后注意双向链表的连接。

这道题目也没什么好说的,先用 preorder
把数字取出来放在一个arraylist里面,然后再一个个取出来形成他要的形状。。。

5

Anyway, Good luck, Richardo!

还是写的时候想的太简单了。这道题目要求是 in place.相应的解法是,

6

public class Solution { public void flatten(TreeNode root) { if (root == null) return; flattenTree; } public TreeNode flattenTree(TreeNode root) { if (root == null) return null; TreeNode leftTail = flattenTree(root.left); TreeNode rightTail = flattenTree(root.right); if (leftTail == null && rightTail == null) return root; else if (leftTail == null && rightTail != null) return rightTail; if (leftTail != null) { TreeNode temp = root.right; root.right = root.left; root.left = null; leftTail.right = temp; } if (rightTail != null) return rightTail; else return leftTail; }}

题意:用二叉树的右节点当做链表的next节点,把一个二叉树转换为链表的形式。

还是inorder 的思想。所以,inorder
的时候,我们可以先写一些草稿代码。假设我们已经拿到了我们想要的结构。下来该怎么操作?然后,如何返回?这样子的思路,一般都可以把代码写出来的!参考博客:
pre order tree**

思路:
把二叉树转成一个链表的关键点是怎么把左子树连接在根节点和右子树中间。
假设左右子树已经分别转为链表了,那么如果知道了这个链表的头部和尾部,用根节点连接左子树链表的头部,再用左子树链表的尾部连接右子树链表的头部,就完成了二叉树到链表的转换。
因此可以用分治的方法解决这道题,先求左右子树转换成的链表,这个链表需要定义一个结构来标记头和尾,再把根节点和两个链表连接起来,返回给上一层连接后的链表结构。
分治的时候要注意左右子树为空的情况,不同的情况,头和尾指向哪里是不一样的。

Anyway, Good luck, Richardo!

class Result {
    TreeNode head;
    TreeNode tail;
}

public void flatten(TreeNode root) {
    helper(root);
}

public Result helper(TreeNode root) {
    if (root == null) {
        return null;
    }
    //初始化当前链表的头尾
    Result res = new Result();
    res.head = root;
    res.tail = root;
    //求左右子树转换的链表
    Result left = helper(root.left);
    Result right = helper(root.right);
    //不同情况下,连接根节点和左右链表,并更新当前链表尾部
    if (left != null && right != null) {
        root.right = left.head;
        root.left = null;
        left.tail.right = right.head;
        res.tail = right.tail;
    } else if (root.left != null) {
        root.right = left.head;
        root.left = null;
        res.tail = left.tail;
    } else if (root.right != null) {
        root.right = right.head;
        res.tail = right.tail;
    }

    return res;
}

My code:

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode { val = x; } * } */public class Solution { public void flatten(TreeNode root) { if (root == null) { return; } helper; } private TreeNode helper(TreeNode root) { if (root == null) { return null; } TreeNode temp = helper(root.left); if (temp == null) { TreeNode right = helper(root.right); return right == null ? root : right; } temp.right = root.right; root.right = root.left; root.left = null; TreeNode right = helper(temp.right); return right == null ? temp : right; }}

思路还是比较清晰的。就是拿recursion做。然后发现答案里面竟然可以拿iteration做。。。

My code:

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode { val = x; } * } */public class Solution { public void flatten(TreeNode root) { if (root == null) { return; } while (root != null) { TreeNode curr = root.left; if (curr != null) { while (curr.right != null) { curr = curr.right; } curr.right = root.right; root.right = root.left; root.left = null; } root = root.right; } }}

reference:

感觉还是很巧妙地。

和recursion的主要区别在于,recursion
是从底部开始flatten而iteration是从顶部开始flatten

Anyway, Good luck, Richardo! — 09/07/2016

My code:

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode { val = x; } * } */public class Solution { public void flatten(TreeNode root) { if (root == null) { return; } flatten(root.left); flatten(root.right); TreeNode temp = root.right; root.right = root.left; root.left = null; while (root.right != null) { root = root.right; } root.right = temp; }}

reference:

之前的做法太难理解了。这个很直观。记住。

iteration 的做法也很巧妙。

Anyway, Good luck, Richardo! — 09/25/2016

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图