随想录刷题笔记 —二叉树篇8 654最大二叉树 530二叉搜索树最小绝对差 501二叉搜索树中的众数

654最大二叉树

递归：切割数组传入

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        if(nums.length==0){
            return null;
        }
        int maxval = nums[0];
        int maxind = 0;
        for (int i = 1; i < nums.length; i++) {
            if (maxval<nums[i]){
                maxval=nums[i];
                maxind = i;
            }
        }
        TreeNode node = new TreeNode(maxval, null, null);
        node.left = constructMaximumBinaryTree(Arrays.copyOfRange(nums, 0, maxind));
        node.right = constructMaximumBinaryTree(Arrays.copyOfRange(nums, maxind+1, nums.length));
        return node;
    }
}

优化：传入左右边界

class Solution {
    int leftindex = 0;
    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return cMBinaryTree(nums, nums.length);
    }

    public TreeNode cMBinaryTree(int[] nums, int rightindex) {
        if(leftindex==rightindex){
            return null;
        }
        
        int maxval = nums[leftindex];
        int maxind = leftindex;
        for (int i = leftindex; i < rightindex; i++) {
            if (maxval<nums[i]){
                maxval=nums[i];
                maxind = i;
            }
        }
        TreeNode node = new TreeNode(maxval, null, null);
        node.left = cMBinaryTree(nums, maxind);
        leftindex = maxind+1;
        node.right = cMBinaryTree(nums, rightindex);
        return node;
    }
}

530二叉搜索树最小绝对差

设置prenode结点，用于标记仅比此节点小的结点，使用中序遍历从而保证prenode结点的标记成立。

class Solution {
    int mindiff = 100000;
    TreeNode prenode = null;
    public int getMinimumDifference(TreeNode root) {
        if (root == null) return 0;
        getMinimumDifference(root.left);
        if (pre != null && root.val - pre.val < res) {
            res = root.val - pre.val;
        }
        pre = root;
        getMinimumDifference(root.right);
        return res;
    }
}

501二叉搜索树中的众数

中序遍历：使用prenodemode标记前序结点，maxmode表示最大出现次数, countmode表示前序结点出现次数。

比较该节点和前序结点是否值相同，相同则countmode++。

比较maxmode和countmode大小，大于则清空结果集合，插入该元素，等于则直接插入。小于则忽略。

class Solution {
    public int[] findMode(TreeNode root) {
        fMode(root);
        int[] res = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            res[i] = ans.get(i);
        }
        return res;
    }
    int countmode = 0;
    int maxmode = 0;
    TreeNode prenodemode = null;
    ArrayList<Integer> ans = new ArrayList<Integer>();
    public void fMode(TreeNode root) {
        if (root.left != null) {
            fMode(root.left);
        }
        if (prenodemode!=null&&prenodemode.val==root.val){
            countmode++;
        }
        else countmode=1;
        if (countmode==maxmode){
            ans.add(root.val);
        }else
            if (countmode>maxmode){
            ans.clear();
            ans.add(root.val);
            maxmode = countmode;
            }
        
        prenodemode = root;
        if (root.right != null) {
            fMode(root.right);
        }
    }
}

收获

二叉搜索树和前序遍历很适配