Lexi's Leetcode solutions

Posts Tagged ‘topDown

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