将二叉树展平到链表

Question

给定一棵二叉树，将其展平为就地的链表。

例如，给定以下树：

    1
   / \
  2   5
 / \   \
3   4   6

被压扁的树应该是这样的：

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

我对其他解决方案很感兴趣，但我想问，为什么在运行代码时，输出只与输入树匹配。

public void flatten(TreeNode root) {
        if(root == null)
            return;
        TreeNode newRoot = new TreeNode(root.val);
        List<TreeNode> list = new ArrayList<>();

        helper(root,list);
        TreeNode current = newRoot;
        for(int i = 1; i < list.size();i++) {
            current.right = new TreeNode(list.get(i).val);
            current = current.right;
        }
        root = newRoot;
    }

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

Answer 1

当您重新分配作为参数传递给方法的引用时，它在该方法之外没有任何效果。所以你的上一个作业root=newRoot 不会在flatte（）方法之外产生任何效果。如果创建另一个节点，则需要更改根对象的链接。

TreeNode root = new TreeNode(10);
flatten(root);

调用flattenroot后，将指向与调用前完全相同的对象。您可以尝试执行以下操作，而不是root=newRoot

root.right = newRoot.right;
root.left = newRoot.left;