Binary tree paths, BFS solution


  • 1
    X
    class Solution {
    public:
        vector<string> binaryTreePaths(TreeNode* root) {
            // Write your code here
            vector<string> res;
            if (root == NULL) return res;
            queue<pair<string, TreeNode*>> Q;
            Q.push({to_string(root->val), root});
            
            while (!Q.empty()) {
                string curStr = Q.front().first;
                TreeNode* curNode = Q.front().second;
                Q.pop();
                
                if (curNode->left == NULL && curNode->right == NULL) {
                    res.push_back(curStr);
                } else {
                    if (curNode->left != NULL)
                        Q.push({curStr + "->" + to_string(curNode->left->val), curNode->left});
                    if (curNode->right != NULL)
                        Q.push({curStr + "->" + to_string(curNode->right->val), curNode->right});
                }
            }
            
            return res;
        }
    };

  • 0

    Thanks for sharing! Since in Java we don't have Tuple or Pair, I try using two Queues which seems a little messy.

        public List<String> binaryTreePaths(TreeNode root) {
            List<String> ret = new ArrayList<>();
            Queue<TreeNode> nodes = new LinkedList<>();
            Queue<String> paths = new LinkedList<>();
            if (root != null) {
                nodes.offer(root);
                paths.offer(String.valueOf(root.val));
            }
            while (!nodes.isEmpty()) {
                TreeNode node = nodes.poll();
                String path = paths.poll();
                if (node.left == null && node.right == null) {
                    ret.add(path);
                } else {
                    if (node.left != null) {
                        nodes.offer(node.left);
                        paths.offer(path + "->" + node.left.val);
                    }
                    if (node.right != null) {
                        nodes.offer(node.right);
                        paths.offer(path + "->" + node.right.val);
                    }
                }
            }
            return ret;
        }
    

Log in to reply
 

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