114. 二叉树展开为链表#

class Solution {
    public void flatten(TreeNode root) {
        // 按前序遍历顺序保存所有节点，后续按顺序重连
        List<TreeNode> list = new ArrayList<>();
        // 收集前序遍历节点序列
        preOrder(root, list);

        // 依次把每个节点指向序列中的下一个节点
        for (int i = 0; i < list.size()-1; i++) {
            // 当前节点
            TreeNode curr = list.get(i);
            // 按题意展开后左指针必须为 null
            curr.left = null;
            // 右指针指向前序序列中的下一个节点
            curr.right = list.get(i+1);
        }
    }

    private void preOrder(TreeNode node, List<TreeNode> list) {
        // 递归终止：空节点直接返回
        if (node == null) return;
        // 前序：先记录当前节点
        list.add(node);
        // 再遍历左子树
        preOrder(node.left, list);
        // 最后遍历右子树
        preOrder(node.right, list);
    }
}

初始状态：
    1
   / \
  2   5
 / \   \
3   4   6

第1步：处理节点1
左子树最右节点是4
将5接到4的右侧：
    1
   / 
  2   
 / \   
3   4
     \
      5
       \
        6
然后左子树移到右侧：
    1
     \
      2   
     / \   
    3   4
         \
          5
           \
            6

第2步：处理节点2
同理操作后变为：
    1
     \
      2
       \
        3
         \
          4
           \
            5
             \
              6

class Solution {
    public void flatten(TreeNode root) {
        // curr 用于沿着“展开后的右链”一路向下处理
        TreeNode curr = root;
        // 遍历整棵树，直到没有后续节点
        while (curr != null) {
            // 只有存在左子树时才需要重组
            if (curr.left != null) {
                // predecessor 指向当前节点左子树的最右节点（前驱节点）
                TreeNode predecessor = curr.left;
                // 持续向右走到最右端
                while (predecessor.right != null) {
                    predecessor = predecessor.right;
                }

                // 1) 把当前节点原右子树挂到前驱节点右侧
                predecessor.right = curr.right;
                // 2) 把当前节点左子树整体移动到右侧
                curr.right = curr.left;
                // 3) 按题意清空左指针
                curr.left = null;
            }
            // 移动到下一个节点（始终沿右指针前进）
            curr = curr.right;
        }
    }
}