[leetcode] PathSum | 找从root到leaft的加和==x的路径是否存在
Posted August 4, 2013
on:本来觉得是弱智题,但是基本从来不top down的做树的题,写完还真挂在bug上了。
top down利用leaf的树题一般是这样的pattern:
void topDown(Node node) { if (node == null) //this means reaching a branch that only one side has something, the other side is this (null) if (node.left == null && root.right == null) //this is leaf, do something, then return; topDown(node.left); topDown(node.right); }
和平时做的preorder(中左右)的区别:preOrder这种遍历下来,的确会在empty node的时候停,但是不能判断什么时候到了叶子节点。而topDown利用了叶子节点的定义来判断当前节点是否叶子,可以这时候做一些运算。
void preOrder(Node node) { if (node == null) //this could either mean parent is a leaf, or parent's this branch is empty but has another child } preOrder(node.left); preOrder(node.right); }
Leave a Reply