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

Posted by: lexigrey on: August 4, 2013

• In: leetcode
• Leave a Comment

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

Advertisements

Tags: easy, topDown, tree