美文网首页
代码随想录算法训练营第20天|二叉树part06

代码随想录算法训练营第20天|二叉树part06

作者: pangzhaojie | 来源:发表于2023-06-08 10:53 被阅读0次

最大二叉树

     public TreeNode constructMaximumBinaryTree(int[] nums) {
    return cons(nums, 0, nums.length);
}

private TreeNode cons(int[] nums, int begin, int end) {
    if(begin >= end) {
        return null;
    }
    int maxValue = nums[begin];
    int maxIndex = begin;
    for(int i = begin; i < end;i++) {
        if(nums[i] > maxValue) {
            maxValue = nums[i];
            maxIndex = i;
        }
    }
    TreeNode root = new TreeNode(maxValue);
    root.left = cons(nums, begin, maxIndex);
    root.right = cons(nums, maxIndex + 1, end);
    return root;
}

合并二叉树

    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
    if(root1 == null) {
        return root2;
    }
    if(root2 == null) {
        return root1;
    }
    root1.val = root1.val + root2.val;
    root1.left = mergeTrees(root1.left, root2.left);
    root1.right = mergeTrees(root1.right,root2.right);
    return root1;
}

二叉搜索树搜索

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

}

验证二叉搜索树

     private TreeNode pre = null;
public boolean isValidBST(TreeNode root) {
    if(root == null) {
        return true;
    }
    if(!isValidBST(root.left)) return false;
    if(pre != null && pre.val >= root.val) {
        return false;
    } else {
        pre  = root;
    }
    return isValidBST(root.right);
}

相关文章

  • 【算法题】递归求二叉树深度

    二叉树的深度算法,是二叉树中比较基础的算法了。对应 LeetCode 第104题。 然后你会发现 LeetCode...

  • 数据结构之树的相关问题

    实验要求 实现二叉树的抽象数据类型 实现二叉树的建立的运算 实现二叉树的遍历运算 实现创建哈夫曼树的算法 实验代码...

  • 每日Leetcode—算法(10)

    100.相同的树 算法: 101.对称二叉树 算法: 104.二叉树的最大深度 算法: 107.二叉树的层次遍历 ...

  • 每日Leetcode—算法(11)

    110.平衡二叉树 算法: 111.二叉树的最小树深 算法: 112.路径总和 算法:

  • 我对递归的三重理解

    第一重:二叉树的先序遍历 递归代码: 第二重:从二叉树的角度理解递归算法 举例:Generate Parenthe...

  • 二叉树 for iOS (Swift篇)

    学习了二叉树的概念及二叉树算法习题后, 结合学习的知识通过代码实现一些功能。 二叉树说白了是考验程序员的递归思维,...

  • Algorithm小白入门 -- 二叉树

    二叉树二叉树构造二叉树寻找重复子树 1. 二叉树 基本二叉树节点如下: 很多经典算法,比如回溯、动态规划、分治算法...

  • 深入浅出二叉树遍历的非递归算法 2019-11-15(未经允许,

    1、二叉树遍历的递归算法 递归实现二叉树的遍历非常直观,回顾一下递归的代码: 前序遍历 中序遍历 后序遍历 他们的...

  • 二叉树的基本算法

    二叉树的基本算法 树、二叉树 的基本概念,参考数据结构算法之美-23讲二叉树基础(上):树、二叉树[https:/...

  • 二叉树的遍历

    前言 二叉树和链表在历年春招笔试中,都是重点考核对象。链表由于算法简单,一般考代码实现能力。二叉树考核遍历。 二叉...

网友评论

      本文标题:代码随想录算法训练营第20天|二叉树part06

      本文链接:https://www.haomeiwen.com/subject/qitjedtx.html