114. 二叉树展开为链表

题目描述

给定一个二叉树，原地将它展开为链表。

例如，给定二叉树

	    1
	   / \
	  2   5
	 / \   \
	3   4   6

将其展开为：

	1
	 \
	  2
	   \
	    3
	     \
	      4
	       \
	        5
	         \
	          6

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

以下思路参考windliang，他写得很详细，我下面的思路就有点简略了，下面的代码是我根据思路自己写的。

我的思路

二叉树展开之后，从根节点遍历到叶子结点的顺序，正好就是原二叉树的先序遍历。

思路一（含代码）

1. 把根结点的右子树，接到根结点左子树的最右叶子结点的右链接。
2. 把根节点的左子树接到根结点右链接上。
3. 根结点更新为根结点的右子结点，重复上述步骤，直到当前的根结点为空。

原二叉树：
	    1
	   / \
	  2   5
	 / \   \
	3   4   6

1. 将根结点 1 的右子树，接到根结点左子树的最右叶子结点 4 的右链接。
		1
	   / 			
	  2   			5
	 / \   			 \
	3   4   		  6	

		1
	   / 			
	  2   			
	 / \   			 
	3   4   
	     \
	      5
	       \
	        6		  
2. 把根节点的左子树接到根结点 1 右链接上。
	 1	 	 2          
		    / \          
		   3   4  
		        \
		         5
		          \
		           6
	    
       1
	    \
	     2          
	    / \          
	   3   4  
	        \
	         5
	          \
	           6
            
3. 根结点更新为根结点的右子结点 2，重复上述步骤：把 2 结点的右子树拿出来，
   接到 2 结点左子树的最右叶子结点 3 的右链接。
	   1			4
	    \			 \
	     2            5
	    /              \
	   3   			    6
        
 	   1			
	    \			 
	     2            
	    /              
	   3   	
	   	\
         4  
          \
           5
            \
             6 	    

4. 把 2 节点的左子树接到当前根结点 2 右链接上。
 	   1			3
	    \			 \
	     2            4
	                   \
	    	 			5
						 \    
						  6
	1
     \
      2          
       \          
        3      
         \
          4  
           \
            5
             \
              6         

下面省略，自己推导。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {    
    public void flatten(TreeNode root) {
        // 先找到根节点的右节点
        while(root != null){
            if(root.left != null){
            	TreeNode pointer = root.left; // 用来寻找根结点左子树的最右结点
                while(pointer.right != null){   // 寻找左子树的最右结点
                    pointer = pointer.right;
                }
                pointer.right = root.right;   // 1. 左子树的最右结点右链接，指向当前根结点的右结点
                root.right = root.left;	// 2. 将当前根结点的左子树变为右子树
                root.left = null;	// 记得将根节点的左链接写空
            }
            root = root.right;	// 3. 更新根结点为根结点的右子结点
        }
    }  
}

思路二（含代码）

能否利用先序遍历呢？
先找到第一个结点 1 ，然后知道第二个结点 2 ，让结点 1 的右链接指向 结点 2 ，以此类推。但是这个过程有一个问题，当结点 1 的右链接指向结点 2 时，原来结点 1 的右子树就会丢失了。

原来的想法是先序遍历找到1 2 3 4 5 6，然后连接起来；如果改成后序遍历，就可以解决上述问题。注意：这边的后序遍历和常规的后序遍历略有不同。先序遍历是根结点->左子结点->右子结点，这边的后序遍历就是先序遍历的逆序，即右子结点->左子结点->根结点。

先找到结点 6 ，然后找到 5 ，让结点5指向结点6，就像：6 5 4 3 2 1 => 6<-5 4 3 2 1 => 6<-5<-4 3 2 1 ······

这样就不会丢失右子树了，因为右子树已经访问过了。

递归的代码如下：

class Solution {    
    TreeNode pre = null;	// 用于保存前一个访问过结点
    public void flatten(TreeNode root) {
        if(root == null)    return;        
        flatten(root.right);	// 遍历右子树
        flatten(root.left);		// 遍历左子树
        root.right = pre;	// 当前结点的右链接指向上一个访问过的结点
        root.left = null;	// 当前结点的左节点为空，因为左节点已经访问过了，所以这样做没有关系
        pre = root;	// 保存当前结点为下一次递归的上一个节点
    } 
}

迭代写法:

class Solution {        
    public void flatten(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        TreeNode pre = null;
        TreeNode cur = root;
        while(cur != null){ // 将根结点以及所有子孙右结点全部存入栈中
            stack.push(cur);
            cur = cur.right;
        }
        while(!stack.empty()){
            cur = stack.peek();
            // 当前结点的左节点为空，或者已经被访问过
            if(cur.left == null || cur.left == pre){
                stack.pop();
                cur.right = pre;	// 当前结点的右链接指向上一个访问过的结点
                cur.left = null;
                pre = cur;
            }else{	// 如果结节点没有访问过，则把左结点，及它的所有子孙右结点全部压栈
                cur = cur.left;
                while(cur != null){
                    stack.push(cur);
                    cur = cur.right;
                }
            }
        }
    }       
}

如有不当之处，欢迎读者批评指正！