二叉树展开为单链表

思路：

1.先进行计数一下二叉树的节点的个数（递归）

2.开一个用于存树的节点的容器数组

3.将二叉树的节点存入数组容器中

4.再将二叉树的展开为单链表

代码：

import java.util.*;
import java.util.ArrayList;
/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
public class Solution {
    //定义一个变量number用于记录树的节点的个数
    public int number=0;
    //定义一个函数用于计数树中的节点个数
    //只要根节点不为空，就进行计数加一
    //进行递归计数，先计数左树的节点的个数，递归计数右树的节点的个数
    public void Countnodes(TreeNode root){
        if(root!=null){
            number++;
        }else{
            return;
        }
        Countnodes(root.left);
        Countnodes(root.right);
    }
    //传入需要展开的树的根节点和容器
    //doexpandtree()函数，就是将二叉树中的节点存入到数组中
    public void doexpandtree(TreeNode root,ArrayList<TreeNode> treenodelist){
        //如果树为空，就不需要进行展开
          if(root!=null){
            treenodelist.add(root);
          }else{
            return;
          }
          //否则如果根的左子树不为空，就进行展开
          //如果根的右子树不为空，就进行展开
          if(root.left!=null){
            doexpandtree(root.left,treenodelist);
          }
          if(root.right!=null){
            doexpandtree(root.right,treenodelist);
          }
    }
    public void expandTree (TreeNode root) {
        //判断一下如果树为空，就直接不需要进行展开为二叉树
        if(root==null){
            return;
        }
        //先计数一下该树的节点的个数
        Countnodes(root);
        //创建一个用于存树节点的数组链表，因为需要将二叉树展开为单链表的形式存在数组链表中
        //所以需要知道该树有多少个节点
        ArrayList <TreeNode> treenodelist=new ArrayList<>(number);
        //将二叉树展开为单链表
        doexpandtree(root,treenodelist);
        //将二叉树展开为单链表，将根节点的左指针指向null
        TreeNode cur=root;
        cur.left=null;
        //之后就将每个节点的左指针指向null，将每个节点的右指针指向下一个节点
        for(int i=1;i<treenodelist.size();i++){
             cur.right=treenodelist.get(i);
             cur.right.left=null;
             cur=cur.right;
        }
        
    }
}