文章目录

• 力扣算法学习day18-2
• • 108-将有序数组转换为二叉搜索树
  • • 题目
    • 代码实现
  • 538-把二叉搜索树转换为累加树
  • • 题目
    • 代码实现
    • • 已复习 代码随想录-二叉树总结篇

力扣算法学习day18-2

108-将有序数组转换为二叉搜索树

题目

代码实现

/**
 * 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 sortedArrayToBST(int[] nums) {
        return buildTree(nums,0,nums.length-1);
    }
    public TreeNode buildTree(int[] nums,int left,int right){
        if(left == right){
            return new TreeNode(nums[left]);
        }
        if(left > right){
            return null;
        }

        int index = left + (right - left)/2;
        TreeNode root = new TreeNode(nums[index]);
        root.left = buildTree(nums,left,index-1);
        root.right = buildTree(nums,index+1,right);

        return root;
    }
}

538-把二叉搜索树转换为累加树

题目

代码实现

/**
 * 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 {
    // 自己直接想到的办法
    // int sum;
    // public TreeNode convertBST(TreeNode root) {
    //     // 先求得总共的值
    //     sum = postOrder(root);
    //     infixOrderChangeValue(root);
    //     return root;
    // }
    // public int postOrder(TreeNode node){
    //     if(node == null){
    //         return 0;
    //     }
    //     int leftValue = postOrder(node.left);
    //     int rightValue = postOrder(node.right);
    //     return leftValue + rightValue + node.val;
    // }
    // public void infixOrderChangeValue(TreeNode node){
    //     if(node == null){
    //         return;
    //     }

    //     infixOrderChangeValue(node.left);

    //     int temp = node.val;
    //     node.val = sum;
    //     sum = sum - temp;

    //     infixOrderChangeValue(node.right);
    // }

    // 速度优化,代码精简，思路提升。从后往前累加(把搜索树看成一个数组，中序反过来累加即可)。 1ms -> 0ms
    TreeNode pre;
    public TreeNode convertBST(TreeNode root) {
        reverseInfixOrderChangeValue(root);
        return root;
    }
    public void reverseInfixOrderChangeValue(TreeNode node){
        if(node == null){
            return;
        }

        reverseInfixOrderChangeValue(node.right);// 右

        if(pre != null){//中
            node.val = node.val + pre.val;
        }
        pre = node;
        
        reverseInfixOrderChangeValue(node.left);// 左
    }
}

已复习 代码随想录-二叉树总结篇