【每日阅读】2020年11月10日-二叉树原地展开为链表

链接

https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/

新得

这个题目注明了，需要原地展开，也就是不使用新得内存空间，使用原来二叉树的节点来展开。展开后的树其实特征很明显

1. 每个节点只有右节点有值
2. 新展开的树从上到下的节点顺序是先序遍历的顺序

树的题目一开始就往三种遍历（先序、中序、后序）顺序去想大概率会命中，这道题就是使用先序遍历的思路可以解决。

思路

当使用先序遍历的方式遍历每个节点时，将每次访问的节点从树上摘除，然后挂到新树上，再继续访问左子树，右子树，重复同样的操作（递归）即可。

代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private TreeNode rightLastNode;

    /**
     * 先序遍历搞定树的展开
     */
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }

        TreeNode left = root.left;
        TreeNode right = root.right;

        if (rightLastNode != null) {
            rightLastNode.right = root;
        }

        rightLastNode = root;

        root.left = null;
        root.right = null;

        flatten(left);
        flatten(right);
    }
}