/** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ // rule in result vector during iteration: // single path: 0; ----> v0 // cross path: 1; ----> v1 // single point: 2; ----> v2 // lonely path: 3; ----> v3 class Solution { public: int maxPathSum(TreeNode *root) { vector<int> *rv = mps(root); int r = miv(*rv); delete rv; return r; } vector<int> *mps(TreeNode *root) { if(!root) return NULL; vector<int> *ret = new vector<int>; vector<int> *lr = mps(root->left); vector<int> *rr = mps(root->right); vector<int> v0; v0.push_back(root->val); if(lr) v0.push_back(root->val + (*lr)[0]); if(rr) v0.push_back(root->val + (*rr)[0]); vector<int> v1; if(lr) v1.push_back((*lr)[1]); if(rr) v1.push_back((*rr)[1]); if(lr && rr) v1.push_back((*lr)[0] + (*rr)[0] + root->val); vector<int> v2; v2.push_back(root->val); if(lr) v2.push_back((*lr)[2]); if(rr) v2.push_back((*rr)[2]); vector<int> v3; if(lr) { v3.push_back((*lr)[0]); v3.push_back((*lr)[3]); } if(rr) { v3.push_back((*rr)[0]); v3.push_back((*rr)[3]); } ret->push_back(miv(v0)); ret->push_back(miv(v1)); ret->push_back(miv(v2)); ret->push_back(miv(v3)); delete lr; delete rr; return ret; } // max in vector int miv(vector<int> l) { int m = INT_MIN; vector<int>::const_iterator cit = l.begin(); while(cit != l.end()) { m = *cit > m ? *cit : m; cit ++; } return m; } };
相关推荐
2.4.3 查找数组中的最大值 68 2.4.4 查找数组中第k个最小值 69 2.5 组织数据 71 2.6 更多示例 75 2.6.1 Fibonacci数列(兔子繁殖) 75 2.6.2 组织游行队伍 78 2.6.3 从n个事物中选出k个 79 2.7 递归和效率 81 ...
本文主要讨论二叉搜索树的基本性质以及基本操作,并用C++代码实现,每个成员... 包括: 普通二叉树的遍历(先序,中序,后序,分层),二叉搜索树的建立,插值,删值,求前驱,求后继,求size,求最大节点,最小节点
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。节点不为空时则分别求左右子树的高度的最大值,同时加1表示当前节点的高度,返回该数值代码* Definit
编写一个C++程序,它能根据读入的某二叉树的中序序列和后序序列(两个英文字母串,每个串长不大于80,各占一行),构造该二叉树,并输出该二叉树的前序序列、叶的个数、二度结点个数及其从根节点开始的最长路径上...
5.4.5 根节点到叶结点的所有路径代表的数字之和 6. 排序 6.1 合并两个有序数组到其中一个数组 6.2 合并两个有序链表 6.3 合并K个有序链表 6.4 使用插入排序来排序链表 6.5 归并排序排序链表 6.6 第一个缺少的正数 ...
leetcode 338 个人博客: 坚持每天更新一至两篇。向更优算法迈进~ LeetCode 思路方法。代码以C++,Python,Java为主 更新于:2018-11-12 题目 Difficulty C++ ...二叉树路径和 Easy Pascal三角求和
B. 球最大值函数max:通过单链表的一趟遍历,在单链表中确定值最大的结点; C. 统计函数number:统计单链表中具有给定值x的所有元素数量; D. *建立函数create:根据一维数组a[n]建立一个单链表,使...
查找最大值和最小值 删除节点 二叉树的效率 用数组表示树 重复关键字 完整的tree.java程序 哈夫曼(Huffman)编码 小结 问题 实验 编程作业 第9章 红-黑树 第10章 2-3-4树和外部存储 第11章 哈希表 第12章 ...
查找最大值和最小值 删除节点 二叉树的效率 用数组表示树 重复关键字 完整的tree.java程序 哈夫曼(Huffman)编码 小结 问题 实验 编程作业 第9章 红-黑树 本章讨论的方法 平衡树和非平衡树 使用...
根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者,称为大根堆,又称最大堆(大顶堆)。 大根堆要求 ①根节点的关键字既大于或等于左子树的关键字值,又大于或等于右子树的关键字值。 ②为完全二叉树。
查找最大值和最小值 删除节点 二叉树的效率 用数组表示树 重复关键字 完整的tree.java程序 哈夫曼(Huffman)编码 小结 问题 实验 编程作业 第9章 红-黑树 本章讨论的方法 平衡树和非平衡树 使用...
查找最大值和最小值 删除节点 二叉树的效率 用数组表示树 重复关键字 完整的tree.java程序 哈夫曼(Huffman)编码 小结 问题 实验 编程作业 第9章 红-黑树 第10章 2-3-4树和外部存储 第11章 哈希表 第12章 堆 第13章 ...
查找最大值和最小值 删除节点 二叉树的效率 用数组表示树 重复关键字 完整的tree.java程序 哈夫曼(Huffman)编码 小结 问题 实验 编程作业 第9章 红-黑树 第10章 2-3-4树和外部存储 第11章 哈希表 第12章 ...
二叉树最大路径和 树上的 DFS,返回包括根和一侧的最大和。 计算函数内两边的总和并使用全局最大值进行跟踪。 查词二 从单词开始尝试,然后是 DFS。 中等的 岛屿数量 使用 DFS 检查孤岛并增加计数器。 反向链表 II ...
二分搜索、在滑动窗口中查找最大值、搜索旋转数组、查找最小公数、旋转数组、查找低/高索引、向左移动零、查找最大单笔卖出利润、实施快速排序、合并重叠区间、两个值的总和 2 链表 反转单链表,从链表中删除重复项...
滑动窗口最大值 难的 C++ 268 缺少号码 简单的 锈 287 找到重复的号码 中等的 C 343 整数中断 中等的 锈 344 反转字符串 简单的 C 389 找出差异 简单的 Python3 406 按高度重建队列 中等的 Python3 412 嘶嘶声 简单...
9.Jsp和Servlet中的请求转发分别如何实现。 三、J2EE相关知识 1.介绍J2EE、J2SE、J2SE的区别。 2.J2EE是一种技术还是一种平台,他提供了那些技术。 3.什么是Application Server,它有什么功能和优点。 4.简单...
问题描述: 实现红黑树、二叉搜索树相关算法:插入(红黑树涉及树的调整:左旋、右旋等),删除,搜索(指定Key值节点)。 另外,红黑树实现计算树黑高的算法。 实验要求: 1).插入测试,输入 8,11,17,15,6,1...
首先,将硬币从大到小排序,然后通过从最大的硬币中减去数量来应用 DFS 技术。 记忆被保存为 <以前减去的硬币,当前数量> 并被召回。 4. 总结范围 李斗熙 由于这是一个简单的问题,因此没有具体的方法论。 C++:...
1.2.5. 在二元树中找出和为某一值的所有路径 .............................................. 22 1.2.6. Top K 算法详细解析---百度面试 ......................................................... 29 1.2.7. ...