LeetCode总结 -- 树的求和篇
一般来说这些题目就不用考虑非递归的解法了(尽管事实上道理是跟LeetCode总结 -- 树的遍历篇一样的。仅仅要掌握了应该没问题哈)。
LeetCode中关于树的求和有下面题目:
Path Sum
Path Sum II
Sum Root to Leaf Numbers
Binary Tree Maximum Path Sum
这里就是看看左子树和右子树有没有存在和是sum减去当前结点值得路径。仅仅要有一个存在。那么当前结点就存在路径。
还有一个假设是叶子,那么假设剩余的sum等于当前叶子的值。则找到满足条件的路径,返回true。
还有一个变化就是要把全部路径累加起来,这个事实上就是递归条件要进行调整,Path Sum中是推断左右子树有一个找到满足要求的路径就可以,而这里则是把左右子树的结果相加返回作为当前节点的累加结果就可以。
从分治的角度来看,左右子树的最大路径就是取自己的值加上Max(0,左子树最大路径。右子树最大路径)。这么一想也就不用考虑那么多细节了。
而通过当前节点的最长路径则是自己的值+Max(0,左子树最大路径)+Max(0,右子树最大路径)。
所以整个算法就是维护这两个量,一个是自己加上左或者右子树最大路径作为它的父节点考虑的中间量。还有一个就是自己加上左再加上右作为自己最大路径。详细的实现能够參见Binary Tree Maximum Path Sum。
整体来说,求和路径有下面三种:(1)根到叶子结点的路径。(2)父结点沿着子结点往下的路径。(3)随意结点到随意结点(也就是看成无向图)。
这几种路径方式在面试中常常灵活变化,不同的路径方式处理题目的方法也会略有不同,只是最复杂也就是Binary Tree Maximum Path Sum这样的路径方式。仅仅要考虑清楚仍然是一次递归遍历的问题哈。
相关文章
- Leetcode: Shuffle an Array
- Leetcode: Search in Rotated Sorted Array
- LeetCode Insert Interval
- Remove Linked List Elements -- leetcode
- [LeetCode] Power of Two
- 124、【回溯算法】leetcode ——46. 全排列(C++版本)
- leetcode第282场周赛记录
- 【leetcode】日积月累,每日一题--203. 移除链表元素(DayDayUp 12)
- Remove Duplicates from Sorted Array II -- LeetCode
- Binary Search Tree Iterator -- leetcode
- 【leetcode】160: 相交链表
- [LeetCode] Champagne Tower 香槟塔
- leetcode 15. 3Sum 三数之和(中等)