一. 题目

二. 思路

1. 前序遍历

2. 栈

3. 前驱节点

三. 代码

2. 栈

class Solution
{
    TreeNode vh = new TreeNode(), pre = vh;//虚拟头和存储前一个节点

    void dfs(TreeNode u)
    {
        if (u == null) return;
        if (pre.left != u) pre.left = u;

        pre = u;
        dfs(u.left);
        dfs(u.right);
    }

    public void flatten(TreeNode root)
    {
        vh.left = root;
        dfs(root);
        while (root != null)
        {
            root.right = root.left;
            root.left = null;
            root = root.right;
        }
    }
}

3. 前驱节点

class Solution
{
    public void flatten(TreeNode root)
    {
        TreeNode curr = root;
        while (curr != null)
        {
            if (curr.left != null)//所有右节点都会接到正确位置
            {
                TreeNode next = curr.left;
                TreeNode predecessor = next;
                while (predecessor.right != null)
                {
                    predecessor = predecessor.right;
                }
                predecessor.right = curr.right;
                curr.left = null;
                curr.right = next;
            }
            curr = curr.right;
        }
    }
}