描述

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

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

示例

示例1：
flaten.jpg

  1. 输入：root = [1,2,5,3,4,null,6]
  2. 输出：[1,null,2,null,3,null,4,null,5,null,6]

示例2：

  1. 输入：root = []
  2. 输出：[]

示例3：

  1. 输入：root = [0]
  2. 输出：[0]

提示

  • 树中结点数在范围 [0, 2000] 内
  • -100 <= Node.val <= 100

进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？

解题思路

可以用后序遍历，并维护一个 pre 为前一个遍历的节点，将当前节点的左指针置为空，后指针指向 pre。这样反过来看，最后返回的就是二叉树前序遍历。可以用递归或者迭代来实现。

代码

递归

  1. class Solution {
  2.     TreeNode pre;
  3.     public void flatten(TreeNode root) {
  4.         pre = null;
  5.         dfs(root);
  6.     }
  7.     public void dfs(TreeNode node) {
  8.         if (node == null) return;
  9.         dfs(node.right);
  10.         dfs(node.left);
  11.         node.left = null;
  12.         node.right = pre;
  13.         pre = node;
  14.     }
  15. }

迭代

class Solution {
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        stack.push(root);
        TreeNode prev = null;
        while (!stack.isEmpty()) {
            TreeNode curr = stack.pop();
            if (prev != null) {
                prev.left = null;
                prev.right = curr;
            }
            TreeNode left = curr.left, right = curr.right;
            if (right != null) {
                stack.push(right);
            }
            if (left != null) {
                stack.push(left);
            }
            prev = curr;
        }
    }
}