力扣算法学习day18-2
2022/2/7 20:18:56
本文主要是介绍力扣算法学习day18-2,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
文章目录
- 力扣算法学习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);// 左 } }
已复习 代码随想录-二叉树总结篇
这篇关于力扣算法学习day18-2的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)