Convert from Python to C++

Question

Have written the code for level order traversal of a tree in Python. Trying to convert the same workflow to C++, but getting an error that I have mentioned at the bottom. Need some help in correcting/simplifying the code in C++. Sample i/p and o/p:

Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its level order traversal as:
[
  [3],
  [9,20],
  [15,7]
]

Working Python Code:

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

    def levelOrder(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        if not root: 
            return []
        frontier = [root]
        res = [[root.val]]
        while frontier:
            next = []
            for u in frontier:
                if u.left: next.append(u.left)
                if u.right: next.append(u.right)
            frontier = next
            res.append([node.val for node in next])
        return res[:-1]

C++ code with error:

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        if(root==NULL) return {};

        vector<vector<int>> res;
        res.push_back({root->val});
        vector<TreeNode*> frontier;
        frontier.push_back(root);
        while(!frontier.empty()){
            vector<TreeNode*> next;
            auto u = frontier.begin();
            for(; u != frontier.end() ; u++){
                if(u->left!=NULL) next.push_back(u->left);
                if(u->right!=NULL) next.push_back(u->right);
            }
            frontier = next;
            vector<int> temp;
            while(!next.empty()){
                temp.push_back(next.back()->val);
                next.pop_back();
            }
            res.push_back(temp);
        }
        return res;
    }
};

Error: Char 23: error: request for member 'left' in '* u.__gnu_cxx::__normal_iterator<TreeNode**, std::vector<TreeNode*> >::operator->()', which is of pointer type 'TreeNode*' (maybe you meant to use '->' ?)

You really should not use a `vector` of ordinary pointers. It makes it very difficult to manage the lifetime of the objects pointed to. — David Schwartz, Nov 19 '19 at 05:35
In this case, a `vector` of `std::unique_ptr` is probably best. — David Schwartz, Nov 19 '19 at 18:54

score 0 · Accepted Answer · answered Nov 19 '19 at 07:56

You are making it a lot harder to help you when you don't post code that compiles - it isn't hard to guess and write my own:

struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
};

But if your code can't compile without it, then please don't make me write/guess my own.

Anyway, I looked through your code and found this:

        vector<TreeNode*> frontier;
        ...
            auto u = frontier.begin();
            ...
                if(u->left!=NULL) next.push_back(u->left);

Here your u is a std::vector<TreeNode*>::iterator and not a TreeNode*, so you cannot just grab a TreeNode member out of it. You need to dereference the iterator to get the object it contains (*u) and then use it as a TreeNode*. But due to operator precedence, you have to do it like this:

                if ((*u)->left != NULL) next.push_back((*u)->left);

Oh, and by the way: Why is “using namespace std;” considered bad practice?. Trust me when I say; it is much easier to get into the habit of writing those std:: right away, than try to correct bad behavior after it has been ingrained - learned that the hard way.

Convert from Python to C++

1 Answers1