Java算法题-解析将二叉树展开为链表问题

题目

给定一个二叉树，原地将它展开为一个单链表。展开的顺序应该为前序遍历。

引言

将二叉树展开为链表是一个常见的二叉树操作问题。在解决这个问题时，我们需要按照前序遍历的顺序，将二叉树的节点依次展开。

算法思路

1. 定义一个辅助函数 flattenTree，该函数接受一个根节点 node 作为参数，并返回展开后的链表的尾节点。
2. 在 flattenTree 函数中，首先判断 node 是否为叶子节点，如果是叶子节点，则直接返回该节点。
3. 递归调用 flattenTree 函数来展开左子树，并返回展开后的左子树链表的尾节点。
4. 递归调用 flattenTree 函数来展开右子树，并返回展开后的右子树链表的尾节点。
5. 将根节点的右子树设置为展开后的左子树链表的头节点，并将左子树置空。
6. 返回展开后的链表的尾节点，用于连接上一级的节点。

代码实现

以下是使用 Java 实现的解决方案：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {
        this.val = val;
    }
}

public class FlattenBinaryTree {
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        flattenTree(root);
    }

    private TreeNode flattenTree(TreeNode node) {
        if (node.left == null && node.right == null) {
            return node;
        }
        
        TreeNode leftTail = null;
        if (node.left != null) {
            leftTail = flattenTree(node.left);
            leftTail.right = node.right;
            node.right = node.left;
            node.left = null;
        }
        
        TreeNode rightTail = node.right != null ? flattenTree(node.right) : leftTail;
        
        return rightTail;
    }

    public static void main(String[] args) {
        FlattenBinaryTree solution = new FlattenBinaryTree();

        // 创建一个示例二叉树
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right = new TreeNode(5);
        root.right.right = new TreeNode(6);

        solution.flatten(root);

        // 打印展开后的链表
        TreeNode current = root;
        while (current != null) {
            System.out.print(current.val + " ");
            current = current.right;
        }
    }
}

算法分析

• 时间复杂度：对于每个节点，我们只需遍历一次，因此时间复杂度是O(n)，其中n是二叉树的节点数。
• 空间复杂度：递归调用栈的深度最多为树的高度，所以空间复杂度是O(h)，其中h是二叉树的高度。

示例和测试

假设给定一个示例二叉树 root，如下所示：

        1
       / \
      2   5
     / \   \
    3   4   6

根据算法，我们可以将二叉树展开为链表，并按前序遍历的顺序展开。我们可以使用以下代码进行测试：

public class Main {
    public static void main(String[] args) {
        FlattenBinaryTree solution = new FlattenBinaryTree();

        TreeNode root = new TreeNode(1);
        root.left = a TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right = new TreeNode(5);
        root.right.right = new TreeNode(6);

        solution.flatten(root);

        // 打印展开后的链表
        TreeNode current = root;
        while (current != null) {
            System.out.print(current.val + " ");
            current = current.right;
        }
    }
}

总结

将二叉树展开为链表是一个常见的二叉树操作问题，通常可以使用前序遍历来解决。这个算法的时间复杂度是O(n)，空间复杂度是O(h)，其中n是二叉树的节点数，h是二叉树的高度。解决这个问题有助于理解二叉树的操作和递归算法的应用。