剑指 Offer II 052——展平二叉搜索树

题目详情

剑指 Offer II 052——展平二叉搜索树
给你一棵二叉搜索树请 按中序遍历 将其重新排列为一棵递增顺序搜索树使树中最左边的节点成为树的根节点并且每个节点没有左子节点只有一个右子节点。
对于二叉搜索树的更多内容请查看我的二叉搜索树(BST)详解博文

示例1

示例二

方法一中序遍历之后生成新的树

先使用中序遍历二叉搜索树获得递增的数值排列再遍历排列新建一棵展开的二叉搜索树。

Java完整代码实现

/**
 * 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 increasingBST(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<>();
        
        inorderBST(root, list);  // 获得中序遍历结果
        TreeNode head = new TreeNode(0);
        TreeNode p = head;

        for (Integer a : list) {
            TreeNode treeNode = new TreeNode(a);
            p.right = treeNode;
            p = p.right;
        }
        return head.right;
    }

    public static void inorderBST(TreeNode root, ArrayList list) {
        if (root != null) {
            inorderBST(root.left, list);
            list.add(root.val);
            inorderBST(root.right, list);
        }
    }
}

方法二在中序遍历的过程中改变节点指向

直接看代码吧就是在中序遍历中处理指向。

Java完整代码实现

/**
 * 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 {
    private TreeNode p;  // 私有变量类方法都可以访问
    public TreeNode increasingBST(TreeNode root) {
        TreeNode head = new TreeNode(0);
        p = head;
        inorderBST(root);
        return head.right;
    }
    public void inorderBST(TreeNode root) {
        if (root != null) {
            inorderBST(root.left);
            // 在这里处理就行了
            p.right = root;
            root.left = null;
            p = root;
            inorderBST(root.right);
        }
    }
}

ps:计划每日更新一篇博客今日2023-05-03日更第十七天。
昨日更新
二叉搜索树BST详解