将二叉树展平为链表

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;在flatten()方法之外不会产生任何影响。如果创建另一个节点，则需要更改root对象的链接。

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

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

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