Without any other function declaration -- hybrid traversal


  • 0

    The goal of this solution is "without any sub-routine declaration". (pointless, just for a little fun & diversity :) )

    First of all, this solution is more complicated, and slower. So if you are looking for a code out-smart others, this is not what you want.

    The idea is as follows:

    1. Starting with the given node N, do BFS(or level order traversal) on its left/right child if any:
      a. if the value of child & parent's value +1, store it for next run of BFS. Record how many levels we explore for.
      b. otherwise, invoke recursive call on the child (i.e. DFS). Record the maximum value of all from such recursions.

    2. Repeat 1. until there is no consecutive nodes. The longest consecutive path length rooted N at is the number of iteration.

    3. Return the maximum of values mentioned in 1.a and 1.b.

    The code in C++:

        int longestConsecutive(TreeNode* root) {
            if(!root)return 0;
            vector<TreeNode*> v1, v2; // for BFS : stores nodes at current/next level, respectively
            int ret1=0, ret2=0; //record the value in 1.a, 1.b, respectively
            v1.push_back(root);
            do {
                ++ret1;
                for(const auto& n : v1) {
                    // found consective sequence on left child
                    if(n->left && n->left->val == n->val+1) v2.push_back(n->left); 
                    else ret2 = max(ret2,longestConsecutive(n->left)); //do DFS
    
                    // found consective sequence on right child
                    if(n->right && n->right->val == n->val+1) v2.push_back(n->right);
                    else ret2 = max(ret2,longestConsecutive(n->right)); //do DFS
                }
                v2.swap(v1);
                v2.clear();
            } while(!v1.empty());
            return max(ret1,ret2);
        }
    

    The performance (~60ms) is not as good as simple DFS traversal (~36ms), for using vector<int> drag down the speed badly in vector<TreeNode*>. I tried static array on (int v1[16],v2[16]), and the runtime is evaluated around 40ms. It cannot handle the extreme case although the solution is accepted.(imaging a large perfect tree, where the value of nodes = the level of nodes. there would be 32 nodes at level 6.)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.