Leetcode问题：将二叉树展平为链表

Question

我正在尝试在leetcode上解决这个问题：https://leetcode.com/problems/flatten-binary-tree-to-linked-list/（将二叉树扁平化为linkedlist）

这是我的代码：

class Solution{
   
    TreeNode result;

    public void flatten(TreeNode root) {
        TreeNode res = flattenTree(root, null);
        root = res;
    }

    private TreeNode flattenTree(TreeNode node, TreeNode temp) {

        if (node == null) {
            return node;
        }

        if (result == null) {
            result = new TreeNode(node.val);
            temp = result;
        } else {
            TreeNode result1 = new TreeNode(node.val);
            result.right = result1;
            result = result.right;
            result.left = null;
        }
        flattenTree2(node.left, temp);
        flattenTree2(node.right, temp);
        return temp;
    }
}

我相信这是正确的解决方案，因为在指向

res

后，

root

包含正确格式的树，例如第一个屏幕截图中显示的输入数据。这是方法执行后检查树的屏幕截图。

但是，我仍然得到不正确的答案。 leetcode编译器说root根本没有改变。这就是结果。

不，确定我需要做什么才能让 leetcode 接受才是正确的解决方案。

Answer 1

问题是您正在更新

root

方法内的

flatten

变量。在代码中，您要更新

root

参数，它是

flatten

方法内的局部变量，但此更改不会影响方法外部的原始

root

。为了达到预期的结果，您应该直接修改树结构，而不是尝试重新分配

root

参数。

更新代码：

class Solution {
    public void flatten(TreeNode root) {
        flattenTree(root);
    }

    private TreeNode flattenTree(TreeNode node) {
        if (node == null) {
            return null;
        }

        TreeNode rightSubtree = node.right;

        if (node.left != null) {
            node.right = node.left;
            node.left = null;
            TreeNode lastRight = flattenTree(node.right);
            lastRight.right = rightSubtree;
        }

        if (rightSubtree != null) {
            return flattenTree(rightSubtree);
        }

        return node;
    }
}

上面的代码将通过递归地展平左子树和右子树并相应地更新

right

指针来修改树结构。它不需要返回任何新的节点或树，因为它直接修改输入

root

。