Lexi's Leetcode solutions

[leetcode] PathSum | 找从root到leaft的加和==x的路径是否存在

Posted on: August 4, 2013

本来觉得是弱智题,但是基本从来不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);
}
Tags: , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: