fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. struct TreeNode {
  5.     int val;
  6.     TreeNode* left;
  7.     TreeNode* right;
  8.     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  9. };
  10.  
  11. bool hasPathSum(TreeNode* node, int targetSum, string path, string direction) {
  12.     if (node == nullptr) return false;
  13.  
  14.     path += to_string(node->val) + " ";
  15.  
  16.     if (node->left == nullptr && node->right == nullptr && node->val == targetSum) {
  17.         cout << "Path: " << path << endl;
  18.         cout << "Direction: " << "root"+direction << endl;
  19.         return true;
  20.     }
  21.  
  22.     bool leftPath = hasPathSum(node->left, targetSum - node->val, path, direction + "->left");
  23.     bool rightPath = hasPathSum(node->right, targetSum - node->val, path, direction + "->right");
  24.  
  25.     return leftPath || rightPath;
  26. }
  27.  
  28. int main() {
  29.     TreeNode* root = new TreeNode(10);
  30.     root->left = new TreeNode(8);
  31.     root->right = new TreeNode(2);
  32.     root->left->left = new TreeNode(3);
  33.     root->left->right = new TreeNode(5);
  34.     root->right->left = new TreeNode(2);
  35.  
  36.     int sum = 21;
  37.     string path = "";
  38.     string direction = "";
  39.  
  40.     if (hasPathSum(root, sum, path, direction)) {
  41.         cout << "There is a root to leaf path with sum " << sum << endl;
  42.     } else {
  43.         cout << "There is no root to leaf path with sum " << sum << endl;
  44.     }
  45.  
  46.     return 0;
  47. }
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Path: 10 8 3 
Direction: root->left->left
There is a root to leaf path with sum 21
https://ideone.com/5bPdPB
language:
C++ 4.3.2 (gcc-4.3.2)
created:
34 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!