代码随想录 Day19 - 二叉树（六）
作者：jjn0703
- 2023-07-18 江苏
本文字数：1740 字
阅读完需：约 6 分钟
654. 最大二叉树
/** * 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 constructMaximumBinaryTree(int[] nums) { return buildMaxTreeFromArray(nums, 0, nums.length); } private TreeNode buildMaxTreeFromArray(int[] nums, int start, int end) { if (end - start < 1) { return null; } if (end - start < 2) { return new TreeNode(nums[start]); } int maxIndex = start; int maxNum = nums[start]; for (int i = start; i < end; i++) { if (nums[i] > maxNum) { maxIndex = i; maxNum = nums[i]; } } TreeNode root = new TreeNode(maxNum); root.left = buildMaxTreeFromArray(nums, start, maxIndex); root.right = buildMaxTreeFromArray(nums, maxIndex + 1, end); return root; }}复制代码
617. 合并二叉树
package jjn.carl.binary_tree;
import commons.TreeNode;
/** * @author Jjn * @since 2023/7/18 00:10 */public class LeetCode617 { public TreeNode mergeTrees(TreeNode root1, TreeNode root2) { if (root1 == null) { return root2; } if (root2 == null) { return root1; } TreeNode root = new TreeNode(root1.val + root2.val); root.left = mergeTrees(root1.left, root2.left); root.right = mergeTrees(root1.right, root2.right); return root; }}
复制代码
700. 二叉搜索树中的搜索
递归搜索，比较左子树与根节点，右子树与根节点。
/** * 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 searchBST(TreeNode root, int val) { if(root == null) { return null; } if(root.val == val) { return root; } if(root.val < val) { return searchBST(root.right, val); } return searchBST(root.left, val); }}复制代码
98. 验证二叉搜索树
不断比较左子树的节点值是否在区间，由于节点的值可能是 Integer.MIN_VALUE 或者 Integer.MAX_VALUE，因此需要用 Long 的最大与最小值来比较。
/** * 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 boolean isValidBST(TreeNode root) { return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE); } private boolean isValidBST(TreeNode node, long lower, long upper) { if (node == null) { return true; } if (node.val <= lower || node.val >= upper) { return false; } return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper); }}复制代码
划线
评论
复制
发布于: 刚刚阅读数: 5
版权声明: 本文为 InfoQ 作者【jjn0703】的原创文章。
原文链接:【http://xie.infoq.cn/article/ab48b91191e567284591fa260】。
本文遵守【CC-BY 4.0】协议，转载请保留原文出处及本版权声明。
jjn0703
关注
Java工程师/终身学习者 2018-03-26 加入
USTC硕士/健身健美爱好者/Java工程师.
评论