[数据结构与算法]【一日一题—见微知著】中等题——DFS的思路解决114. 二叉树展开为链表

一、中等题 114. 二叉树展开为链表

1.1 题目要求

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。

1.2 解题思路

官方题解中，采用一个数组保存前序历遍的节点，然后再依次修改节点的左右分支（注意该题是要求对原节点修改）,要求额外的缓存数组。

如果在前序历遍同时，就同时修改节点，比如把左分支设置为null，在修改第1个节点时不仅找不到展开后的右节点，而把左分支设置为null则会导致左分支为搜素丢失。

于是我考虑逆向思维，先DFS到最后一个节点，采用先序历遍的反面——右后序历遍（即右分支-左分支-本节点的顺序），利用一个外部节点记录已经展开好的后面几个节点。
具体过程如下：

1.3 具体实现

官方解法，用数组记录：

class Solution {
    public void flatten(TreeNode root) {
        List<TreeNode> list = new ArrayList<TreeNode>();
        preorderTraversal(root, list);
        int size = list.size();
        for (int i = 1; i < size; i++) {
            TreeNode prev = list.get(i - 1), curr = list.get(i);
            prev.left = null;
            prev.right = curr;
        }
    }

    public void preorderTraversal(TreeNode root, List<TreeNode> list) {
        if (root != null) {
            list.add(root);
            preorderTraversal(root.left, list);
            preorderTraversal(root.right, list);
        }
    }
}

由后向前修改：

class Solution {
    TreeNode curNode;
    public void flatten(TreeNode root) {
        if(root!=null){
            curNode=null;
            DFS(root);
        }
        
    }

    public void DFS(TreeNode node){
        if(node.right!=null){
            DFS(node.right);
        }
        if(node.left!=null){
            DFS(node.left);
        }

        node.right=curNode;
        node.left=null;
        curNode=node;
    }
}

结尾

题目来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems

关注作者，带你刷题，从简单的算法题了解最常用的算法技能（算法题解双日一更）
关注作者刷题——简单到进阶，让你不知不觉成为无情的刷题机器