二叉树展开为链表

原题链接

使用的方法

递归

解题思路

• 给定一个二叉树，我们需要将其展开为一个单链表，要求链表中的节点顺序与二叉树的前序遍历相同。
• 我们可以使用递归来实现这个功能。我们首先递归地展开右子树，然后递归地展开左子树。这样可以确保我们先处理右侧的节点，从而能够正确地连接链表。
• 在递归过程中，我们维护一个指向当前链表头节点的指针。当我们处理当前节点时，我们将其左子树设置为 null，并将其右子树连接到当前链表的头节点上。然后更新链表头节点为当前节点。
• 递归的终止条件是当节点为 null 时，返回。我们首先递归访问右子树，然后递归访问左子树，这样可以确保我们先处理右侧的节点，从而能够正确地连接链表。
• 最后返回展开后的链表头节点作为结果。

代码实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode head;

    public void flatten(TreeNode root) {
        if(root == null)
            return;
        flatten(root.right);
        flatten(root.left);
        root.left = null;
        root.right = head;
        head = root;
    }
}