DAY20|654.最大二叉树,617.合并二叉树,700.二叉搜索树中的搜索,98.验证二叉搜索树

654.最大二叉树

文字讲解最大二叉树

视频讲解最大二叉树

状态:ok

思路:

1、这题和昨天的,通过中序和后序遍历构建二叉树类似,此题相当于通过前序来构建二叉树;但是通过中序和后序来构建二叉树,需要借助两个数组来完成,而此题则需要仅需一个数据可完成;

2、先取数组中的最大值,获取其下标,按照该下标将数组分为左右两个数组,分别为左子树和右子树的元素。

3、然后分别按照步骤2进行递归构建该二叉树并且返回;

class Solution {

    Map<Integer, Integer> valMap = new HashMap<>();

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            valMap.put(nums[i], i);
        }
        return buildMaxTree(nums, 0, nums.length-1);
    }

    public TreeNode buildMaxTree(int[] nums, int startIndex, int endIndex) {
        if (startIndex > endIndex) {
            return null;
        }
        Integer maxNodeVal = getMaxNodeVal(nums, startIndex, endIndex);
        Integer index = valMap.get(maxNodeVal);
        TreeNode root = new TreeNode(maxNodeVal);
        root.left = buildMaxTree(nums, startIndex, index-1);
        root.right = buildMaxTree(nums, index+1, endIndex);
        return root;
    }

    public Integer getMaxNodeVal(int[] nums, int startIndex, int endIndex) {
        int max = Integer.MIN_VALUE;
        for (int i = startIndex; i <= endIndex; i++) {
            if (nums[i] > max) {
                max = nums[i];
            }
        }
        return max;
    }
}

617.合并二叉树

文字讲解合并二叉树

视频讲解代码随想录-合并二叉树

状态:看到这道题有点懵逼,不知道如何下手

思路:

1、强调一下 – T^T — ,递归三部曲,确定好入参,确定好退出条件,确认单层递归逻辑;二刷时不明白再看视频继续加深印象;

代码:

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        return rightMergeLeftTree(root1, root2);
    }


    public TreeNode rightMergeLeftTree(TreeNode leftNode, TreeNode rightNode) {
        if (leftNode == null) return rightNode;
        if (rightNode == null) return leftNode;
        //当两个node都不为空的时候
        leftNode.val = leftNode.val + rightNode.val;
        leftNode.left = rightMergeLeftTree(leftNode.left, rightNode.left);
        leftNode.right = rightMergeLeftTree(leftNode.right, rightNode.right);
        return leftNode;
    }
}

700.二叉搜索树中的搜索

文字讲解二叉搜索树中的搜索

视频讲解代码随想录-二叉搜索树中的搜索

状态:这题so easy了

思路:

1、递归三部曲,入参已确定,判断退出条件为节点为空的时候,递归逻辑为,先判断当前节点的val是否等于搜索值,等于则返回,不等则判断当前node的val比是否比搜索值大,如果大则搜索right子节点,否则搜索left左节点;

代码:

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) return null;
        if (root.val == val) {
            return root;
        }
        if (root.val > val) {
            return searchBST(root.left, val);
        } else {
            return searchBST(root.right, val);
        }
    }
}

98.验证二叉搜索树(重要)

文字讲解验证二叉搜索树

视频讲解 代码随想录-验证二叉搜索树

状态

思路:

1、这题真是给坑就踩进去了,BSF不是简单的理解为每个节点的左子树的值比父节点小,每个节点的右子树比父节点大,而是父节点比左子树的左右节点都大,比右子树的所有节点都小;因为没有考虑全,所以感觉自己没问题,结果调试后一直通过不了;

2、这题通过中序遍历的方式完成,仔细体会代码还能熟悉一下方法栈的调用过程;

3、另外此题还能通过中序遍历将各节点元素收集到一个数组中,然后判断改数组是否是有序的;

代码:

//通过中序遍历+递归的方式判断
class Solution {

    Long maxValue = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        //如果到叶子节点了,则直接返回true;
        if (root == null) {
            return true;
        }
        boolean leftFlag = isValidBST(root.left);
        if (root.val > maxValue) {
            maxValue = Long.valueOf(root.val);
        } else {
            return false;
        }
        boolean rightFlag = isValidBST(root.right);
        return leftFlag && rightFlag;
    }
}

//通过中序遍历收集数组的方式判断
class Solution {


    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return false;
        }
        if (root.left == null && root.right == null) {
            return true;
        }
        List<Integer> params = new ArrayList<>();
        //通过中序遍历收集二叉树元素
        collectParams(root, params);
        return validListSorted(params);
    }

    public void collectParams(TreeNode node, List<Integer> params) {
        if (node == null) {
            return;
        }
        collectParams(node.left, params);
        //收集元素
        params.add(node.val);
        collectParams(node.right, params);
    }

    public boolean validListSorted(List<Integer> list) {
        int left = 0;
        int right = 1;
        while (right <= list.size()-1) {
            if (list.get(left) >= list.get(right)) {
                return false;
            }
            left++;
            right++;
        }
        return true;
    }
}

相关推荐

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-04-09 06:48:03       94 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-04-09 06:48:03       100 阅读
  3. 在Django里面运行非项目文件

    2024-04-09 06:48:03       82 阅读
  4. Python语言-面向对象

    2024-04-09 06:48:03       91 阅读

热门阅读

  1. CV2不同图像插值方式的区别

    2024-04-09 06:48:03       29 阅读
  2. 【R语言基础】如何提取矩阵的上三角矩阵

    2024-04-09 06:48:03       37 阅读
  3. axios-mock-adapter使用

    2024-04-09 06:48:03       39 阅读
  4. ARM的CI-700和Arteris的NoC对比

    2024-04-09 06:48:03       41 阅读
  5. 【华为OD机试】游戏分组、王者荣耀【C卷|100分】

    2024-04-09 06:48:03       36 阅读
  6. Windows安装SSH教程

    2024-04-09 06:48:03       39 阅读
  7. 深度优先搜索算法C实现

    2024-04-09 06:48:03       39 阅读
  8. Stable Diffusion模型基于 TensorFlow 或 PyTorch 训练

    2024-04-09 06:48:03       35 阅读
  9. eclipse怎么配置git

    2024-04-09 06:48:03       31 阅读