二叉树退化成链表

二叉树根据深度优先遍历变成一个链表形式

class Solution {
    List<TreeNode> nodes;
    public void flatten(TreeNode root) {
        nodes = new LinkedList();
        dfs(root);
        int n = nodes.size();
        for(int i = 1; i<n; i++){
            TreeNode pre = nodes.get(i -1) , curr = nodes.get(i);
            pre.left = null;
            pre.right = curr;
        }

    }
    public void dfs(TreeNode root){
        if(root == null){
            return;
        }
        nodes.add(root);
        dfs(root.left);
        dfs(root.right);
    }
}

先进行一个中序遍历，然后再把每个节点的左孩子节点设置为null，右孩子节点设置为下一个节点。