leetcode: Flatten Binary Tree to Linked List

问题描述：

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.

原问题链接：https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

 

问题分析

第一种思路

　　这个问题很容易想到第一种思路。按照前面提示所说到，在前面要求的转换方式里，正好是一个对树进行前序遍历形成的序列。而且这里要求最后形成的队列结构是对应到每个节点的右子节点连接下一个节点。所以我们可以先考虑前序遍历的方式。

　　在前序遍历里，我们每次访问当前的元素之后，就要去访问它的左子节点，然后再去访问它的右子节点。这是一种递归访问的方式。在这里因为要修改节点，使得它成为一个链表，用原生的树前序递归访问的方式不太方便。于是我们可以考虑用非递归的方式来访问它们。同时，在每次访问的时候我们将顺序访问的节点给调整拼接成一个链表。具体来说，针对两个方面。

　　首先，该怎么去遍历它们呢？我们可以采用一个栈，每次访问某个节点的时候，将这个节点的右子节点压入栈中。当然，这是在节点的右子节点存在的情况下。处理完这个节点之后然后继续访问该节点的左子节点。另外，该怎么来根据顺序修改它们的链接呢？一种方式是采用一个队列，每次访问到的元素将它们加入队列。然后再每次从队列里取元素，进行调整。按照这种思路可以实现如下的代码：

 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void flatten(TreeNode root) {
        if(root == null) return;
        TreeNode node = root;
        Deque<TreeNode> stack = new LinkedList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        while(node != null || !stack.isEmpty()) {
            if(node != null) {
                queue.add(node);
                if(node.right != null) stack.push(node.right);
                node = node.left;
            } else if(!stack.isEmpty()) {
                node = stack.pop();
            }
        }
        node = queue.remove();
        node.left = null;
        while(!queue.isEmpty()) {
            TreeNode temp = queue.remove();
            node.right = temp;
            temp.left = node;
            node = temp;
        }
    }
}

 　　实际上，在执行这部分代码的时候，会导致内存的使用超过问题的要求了。因为原问题里要求是in place的方式。所以不能占据太多的内存空间。那么就算是我们采用一个辅助的栈，其对空间的占用也还是会有一定影响的。因此这种方式可以作为实际中的一个解决思路。但是对这个问题并不适用。

 

第二种方法

　　既然前面的那种思路不可行，我们看看还有没有其他的思路。我们看前面调整的过程，对于根节点来说，它的下一个节点在左子节点存在的情况下，就是它的左子节点。所以在变换中会将它的右指针指向它的左子节点。在原来的过程中，将左子节点遍历完之后才会去遍历它的右子节点。所以在左子树中最后遍历的那个节点是它左子节点最右下角的那个节点。

　　这样，我们可以概括出这样的一个过程。每次根据一个节点，找它左子节点的最右下角的元素。如果有，将这个元素的right指向根节点的右子节点。然后根节点的right指向它的左子节点。再指向它的下一个位置。也就是它的right节点。

 　　详细的实现如下：

 

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

 

总结

　　这个问题的实现思路其实不止一种。有通过DFS的方式递归实现的，有通过模拟前序遍历实现的，也有通过发现它的这个规律实现的。重点在于发现具体问题的规律，结合一些数据结构来分析处理。