拍平二叉树

拍平二叉树

问题

这个题目说的是，给你一棵二叉树，你要将它拍平，使得每个节点都只有右子树，并且拍平后的二叉树从上到下的节点是原二叉树前序遍历的结果。

比如说，给你的二叉树是：

      0
    /   \
   1     2
  / \     \
 4   8    16

将它拍平后，得到的二叉树是：

  0
   \
    1
     \
      4
       \
        8
         \
          2
           \
           16

代码

public class AlgoCasts {

  public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
      val = x;
    }
  }

  private void preorder(TreeNode root, List<TreeNode> list) {
    if (root == null) return;
    list.add(root);
    preorder(root.left, list);
    preorder(root.right, list);
  }

  // Time: O(n), Space: O(n)
  public void flattenPreorder(TreeNode root) {
    if (root == null) return;
    List<TreeNode> list = new ArrayList<>();
    preorder(root, list);
    TreeNode cur = root;
    for (int i = 1; i < list.size(); ++i) {
      cur.left = null;
      cur.right = list.get(i);
      cur = cur.right;
    }
  }

  private TreeNode prev = null;

  // Time: O(n), Space: O(n)
  public void flattenReversePreorder(TreeNode root) {
    if (root == null) return;
    flattenReversePreorder(root.right);
    flattenReversePreorder(root.left);
    root.left = null;
    root.right = prev;
    prev = root;
  }

}