PathSum [source code]
public class PathSum {
static
/******************************************************************************/
public class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
return dfs(root, sum, 0);
}
private boolean dfs(TreeNode root, int sum, int accum) {
if (root == null) return false;
accum += root.val;
if (root.left == null && root.right == null && accum == sum) return true;
return dfs(root.left, sum, accum) || dfs(root.right, sum, accum);
}
}
/******************************************************************************/
public static void main(String[] args) {
PathSum.Solution tester = new PathSum.Solution();
}
}
这个题目总体还是很简单的, 刚开始我的一个错误是我希望加一个premature exit, 如果一个 internal node 的 accum 超过了 sum, 就直接退出:
if (accum >= sum && !(root.left == null && root.right == null)) return false;
但是这个有问题, 被[-2, null, -3], -5这个 case 给 break 了, 因为我写这个"超过"的概念的时候, 脑子里默认的其实是所有的 val 都是是nonnegative, 但是这个 assumption 并不对;
最后的速度是1ms (13%);
这个速度基本是 submission 最优解了, 但是代码其实可以写的好看很多:
public class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) return false;
if (root.left == null && root.right == null) return root.val == sum;
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}
}
这样 accum 这个概念就 implicit 了; 不知道这个技巧能不能总结成为更广泛的思路;
discussion 里面也有人想到了这个写法, 并且有人提出:
A:if(root.left == null && root.right == null && sum - root.val == 0) return true;
B:if(root.left == null && root.right == null) return sum == root.val;
这个想法是对的, 因为这个就是以前说的&& in if header的问题; 不过在这里的作用其实是类似的. 就算我们把 B 改成 A, 那么当碰到一个 leaf, 但是不相等的话, 那么 A 就会被跳过, 但是 B 会执行. 尽管在A 的情形下这一行会被跳过, 但是下一个 iteration 的两个 node 都是 null, 直接还是返回 Null, 所以最后的效果是一样的; false(root.left is null) || false(root.right is null) == false (root.val ≠ sum);
这个是 discussion 里面一个iterative PostOrder的解:
class Solution {
public:
bool hasPathSum(TreeNode *root, int sum) {
stack<TreeNode *> s;
TreeNode *pre = NULL, *cur = root;
int SUM = 0;
while (cur || !s.empty()) {
while (cur) {
s.push(cur);
SUM += cur->val;
cur = cur->left;
}
cur = s.top();
if (cur->left == NULL && cur->right == NULL && SUM == sum) {
return true;
}
if (cur->right && pre != cur->right) {
//if right child is not finished: not null and also not finished visiting;
cur = cur->right;
} else {
pre = cur;
s.pop();
SUM -= cur->val;
cur = NULL;
}
}
return false;
}
};
这个 PostOrder 的写法跟G4G 上面看到的不太一样, 不过是正确的; 因为是 PostOrder, 反正这个 prev 是省不了的(用来判断和上一个 iteration 之间的关系). 他这个写法的特点是并不是每一个 iteration 都会 pop (G4G 上面那个就是每一个 iteration 至少都会 pop 一个//这个说法也不对, 并不是确定每一个 iteration 都会 pop);
他这个写法有点像 G4G 的 InOrder 的写法, 稍微有点改进的是, 他把最开始的左边下潜到底的过程整合到了 body 里面(具体做法是加了一个 flag, 这个 flag 只有最开始会被触发(cur != null));//这个理解有问题, 这个左行到底的过程并不是只会发生一次;
这个 postorder 的思路有点像是, 可以说把root.left.left...left这一条 path 当做是一个水平的大梁, 然后所有的 right path 的 branch 就单纯的当做是垂直方向的分支; 从大梁的右边开始, 找到大梁左边的尽头, 然后一点一点的往右边移动, 如果当前 node 有一个向下的 branch, 就下行;
- - - - - - root
| | |
| |
|
其他的就不画了;
重新对这个算法进行理解:
注意这个循环里面, cur实际上是当做一个类似flag的东西来使用了; 哪些iteration开头的时候, cur是Null呢? 其实就是一个向下的大梁走到头的时候, 就设置这个flag; 这样下一个iteration的判断只能依赖对Stack是否Empty的判断, 也就是依赖于, 当前这个vertical的右边是否还有其他的vertical, 也就是horizontal(唯一的一根水平大梁)是否已经走到了头;
这个思路的 PostOrder 其实跟 PreOrder 的写法也非常的类似:
S.create();
S.push(root);
while (not S.isEmpty()) {
current = S.pop() // a retrieving pop
while (current ≠ NULL) {
visit(current);
S.push(current -> right);
current = current -> left
} // end while
} // end while
都是向左走大梁然后回头, 回头的过程中决定是visit 还是下行; 顺序的差别就直接决定了最后是 PostOrder 还是 PreOrder; 注意这里的 push 可以理解为 defer 的意思, 也就是推迟到后面再处理; 这个代码的意思(站在当前 level/node 的逻辑处理, 也就是纯粹用 recursion 的角度来理解的话)就是当我们到了一个 node, 我们先 visit 它(因为是 PreOrder), 然后我们 push(right), 然后我们走到 left. 这样就保证了一个先 left 后 right 的 recurse 的顺序;
严格来说这个好像不是一个左行大梁再回头的思路; 而是一个有序左行的过程;
更进一步, 这个走大梁再回头的思路其实也可以用来理解 InOrder, 具体的代码可以在 bear 上面看, 不过基本的思路是非常类似的: InOrder 的内容其实就是每当到了一个 node 之后, 先 visit, 然后下行, 具体的, 这个是核心代码:
while (node != null) {
stack.push(node);
node = node.left;
}
// traverse the tree
while (stack.size() > 0) {
// visit the top node
node = stack.pop();
System.out.print(node.data + " ");
if (node.right != null) {
node = node.right;
// the next node to be visited is the leftmost
while (node != null) {
stack.push(node);
node = node.left;
}
}
}
同样, 用Verbal Logic来从 recursion 的角度来理解, 好像不太好理解...
稍微总结一下:
- 如果是 PostOrder: 先左行走到大梁尽头, 然后回头. 在某一个 node, 一旦有下行, 下行一格, 然后重复以上内容(左行到头,...). 等到node 下面的内容全部结束的时候(通过 prev 判断), visit node;
- 如果是PreOrder: 有序左行, 碰到一个 node 就 visit 这个 node, 然后 push(defer) 他的 right, 然后进入左边, 重复以上过程. 这个的上行过程稍微有点难以理解:
- - - - - - root
| | |
| |
|
在这样的一个 tree 上画一画; (注意这个例子的选择, 不是过分简单, 也不是过分复杂);
- 如果是 InOrder: 跟 PostOrder 其实非常类似, 左行到大梁尽头, 然后回头. 到达一个 node, 先 vist, 然后一旦有下行, 下行一格, 重复以上步骤; 这样一个步骤就保证了right subtree的处理永远在visit node 之后.
这么总结起来一看, 好像 PreOrder 才是比较特殊的一个;
另外这里的这个 PostOrder 跟 G4G 的 PostOrder 有一个共同点, 就是都很依赖于 peek: 先 peek, 然后再决定是否 pop, 而不是上来就直接 pop 到 current 里面;
每一个 iteration 的逻辑就是: 是否有下行缺口? 如果有, 就下行(这个下行是通过直接的指针移动(cur = cur -> right)来完成的, 而不是通过 Stack 的操作); 如果没有下行, 那么就visit cur. 这样一个让下行判断发生在 vist 之前的顺序,保证了最后的 order 是PostOrder;
为什么这个题目要用 PostOrder? 因为只有有 PostOrder, 你才能在 exit 的时候 undo 在这个 subtree 里发生的change, 也就是这里的SUM -= ...的操作;
相对来说, 可以说 PreOrder 是最好写的.
这个是discussion 上面一个用 PreOrder 来写的:
public boolean hasPathSum(TreeNode root, int sum) {
Stack <TreeNode> stack = new Stack<> ();
stack.push(root) ;
while (!stack.isEmpty() && root != null){
TreeNode cur = stack.pop() ;
if (cur.left == null && cur.right == null){
if (cur.val == sum ) return true ;
}
if (cur.right != null) {
cur.right.val = cur.val + cur.right.val ;
stack.push(cur.right) ;
}
if (cur.left != null) {
cur.left.val = cur.val + cur.left.val;
stack.push(cur.left);
}
}
return false ;
}
注意他这里 right 和 left 的 push 的顺序(如果按照我们之前的代码的思路, 用指针移动来更好理解, 不过如果用 push/defer 的思路, 先 defer right 然后再 defer left 也是可以理解的).
这个算法的思路就是每当走过一个 node(PreOrder 是有序下行, 当然后面还是有一个有序上行的过程), 就把当前的 val 给 push 到下面的 node, 这样最终走到 leaf 的时候, leaf 的 val 就是the sum of the val of all nodes on the path from root to this leaf.
这样一个思路也只能借助于 PreOrder 才能完成, 因为 PreOrder 上行的过程中有一个稍微有点类似level by level的推进过程, 不过这个 leve 并不是 BFS 里面的level, 而是如果按照
- - - - - - root
| | |
| |
|
这个图来看, 可以理解为距离大梁的一个 depth 就算作是一个 level;
比如这个图, PreOrder 最后给出的顺序其实是:
3 2 1
4 5
6
这个算法的一个缺点就是会修改原来的tree, 这个在有些情形下是不允许的;
public boolean hasPathSum(TreeNode root, int sum) {
Stack<TreeNode> stack = new Stack<TreeNode>();
Stack<Integer> sums = new Stack<Integer>();
stack.push(root);
sums.push(sum);
while(!stack.isEmpty()&&(root!=null)){
int value = sums.pop();
TreeNode top = stack.pop();
if(top.left==null&&top.right==null&&top.val==value){
return true;
}
if(top.right!=null){
stack.push(top.right);
sums.push(value-top.val);
}
if(top.left!=null){
stack.push(top.left);
sums.push(value-top.val);
}
}
return false;
}
这个算法通过使用两个 Stack 来解决了这个问题. 这个代码也揭示了这个算法的实质, 其实就跟 recursion 的最简写法是一样的思路; 考虑的更多的是当你在底下某个 level 的 subtree 的时候, 你具有足够的信息就行了, 而不是通过一个 accum 完成一个近似全局的判断; 这个 variation 还是有点不 trivial 的;
Problem Description
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example:
Given the below binary tree and sum = 22,
5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1
return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
Difficulty:Easy
Total Accepted:165.2K
Total Submissions:489.3K
Contributor: LeetCode
Companies
microsoft
Related Topics
tree depth-first search
Similar Questions
Path Sum II Binary Tree Maximum Path Sum Sum Root to Leaf Numbers Path Sum III