LeetCode : 114. Flatten Binary Tree to Linked List 将二叉树转成链表-蒲公英云

LeetCode : 114. Flatten Binary Tree to Linked List 将二叉树转成链表

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

For example, given the following tree:

The flattened tree should look like:

代码
先序遍历是将前一个节点地址记录下来。不过这里边有个注意点就是：你在处理当前节点时会导致上一个节点的left和next值发生变化，需要用tmp变量存一下。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    TreeNode pre = new TreeNode(0);
    TreeNode head = pre;
    public void flatten(TreeNode root) {
        if(root==null) return;
        preOrder(root);
        root = head.right;
    }
    public void preOrder(TreeNode root){
        if(root==null) return;
        TreeNode tmpRight = root.right;
        TreeNode tmpLeft = root.left;
        pre.left = null;
        pre.right = root;
        pre = root;
        preOrder(tmpLeft);
        preOrder(tmpRight);        
    }
}
private TreeNode prev = null;
public void flatten(TreeNode root) {
    if (root == null)
        return;
    flatten(root.right);
    flatten(root.left);
    root.right = prev;
    root.left = null;
    prev = root;
}