DEV Community

dinhluanbmt
dinhluanbmt

Posted on • Updated on

C++ - Basic Tree Traversal(Recursive vs Queue)

LeetCode question :
102. Binary Tree Level Order Traversal
Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level)

Definition for a binary tree node

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};
Enter fullscreen mode Exit fullscreen mode

Recursive Solution

class Solution {
public:
    void visit(TreeNode* root, vector<vector<int>>& ret, int level) {
        if (!root) return;
        while (ret.size() < level + 1) {
            vector<int> v;
            ret.push_back(v);
        }
        ret[level].push_back(root->val);
        visit(root->left, ret, level + 1);
        visit(root->right, ret, level + 1);
    }
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> tree;
        visit(root, tree, 0);
        return tree;
    }
};
Enter fullscreen mode Exit fullscreen mode

Using Queue

class Solution_non_recursive {
public:

    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> retVec;
        if (!root)
            return retVec;
        queue<TreeNode*> q;
        q.push(root);
        int i, size;
        TreeNode* tN;
        while (!q.empty())
        {
            vector<int> tv;
            size = q.size();
            for (i = 0; i < size; ++i)
            {
                tN = q.front();
                q.pop();
                tv.push_back(tN->val);
                if (tN->left) q.push(tN->left);
                if (tN->right) q.push(tN->right);
            }
            retVec.push_back(tv);
        }
        return retVec;
    }
};
Enter fullscreen mode Exit fullscreen mode

Leetcode Question:
104. Maximum Depth of Binary Tree
Given the root of a binary tree, return its maximum depth.
A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Recursive Solution:

class Solution_recursive {
public:
    int getmax(TreeNode* root, int cur){        
        if(!root) return cur;
        return max(getmax(root->left,cur+1),getmax(root->right,cur+1));
    }
    int maxDepth(TreeNode* root) {
        if(!root) return 0;
        return getmax(root,1) -1 ;
    }
};
Enter fullscreen mode Exit fullscreen mode

Using queue

class Solution_queue {
public:    
    int maxDepth(TreeNode* root) {
        int depth = 0;
        if(!root) return depth;
        queue<TreeNode*> mq;
        mq.push(root);
        int size,i;
        TreeNode* tn;
        while(!mq.empty()){
            size = mq.size();
            depth++;
            for(i = 0; i<size;i++){
                tn = mq.front();
                mq.pop();
                if(tn->left) mq.push(tn->left);
                if(tn->right) mq.push(tn->right);
            }
        }     
       return depth;
    }
};
Enter fullscreen mode Exit fullscreen mode

Top comments (0)