leetcode上有道题是关于path sum的，我第一时间的做法是用二叉树的路径去与sum比较。所以需要去打印出二叉树的节点路径，以下是用回溯法。

1 #include
     
       2 #include
      
        3 using namespace std; 4  5 struct TreeNode { 6     int val; 7     TreeNode *left; 8     TreeNode *right; 9     TreeNode(int x) : val(x), left(NULL), right(NULL) {}10     11 };12 class Solution {13 public:14     bool hasPathSum(TreeNode* root, int sum) {15         vector
       
         path;16         path.reserve(100);17         bool flag = false;18         printPaths(root, path, 0);19         return flag;20     }21     void printPaths(TreeNode* node, vector
        
         & path, int pathlen) {22         if (node == NULL) return;23         // append this node to the path array 24         path[pathlen++] = node->val;25         // path.push_back(node->val);26         // it's a leaf, so print the path that led to here  27         if (node->left == NULL && node->right == NULL) {28             printArray(path, pathlen);29         }30         else {31             // otherwise try both subtrees  32             printPaths(node->left, path, pathlen);33             printPaths(node->right, path, pathlen);34             path.pop_back();35         }36     }37     void printArray(vector
         
           &ints, int len) {38         for (int i = 0; i < len; i++) {39              cout << ints[i] << " " ; 40         }41          cout << endl;42     }43 };44 45 int main()46 {47     Solution res;48     TreeNode t1(5);49     TreeNode t2(4);50     TreeNode t3(8);51     TreeNode t4(11);52     TreeNode t5(13);53     TreeNode t6(4);54     TreeNode t7(7);55     TreeNode t8(2);56     TreeNode t9(1);57     t1.left = &t2;58     t1.right = &t3;59     t2.left = &t4;60     t3.left = &t5;61     t3.right = &t6;62     t4.left = &t7;63     t4.right = &t8;64     t6.right = &t9;65     TreeNode * root = &t1;66     bool ret = res.hasPathSum(root,22);67     68     system("pause");69     return 0;70 }
         
        
       
      
     

接着与sum做比较就能知道path sum是否相同了。

1 class Solution { 2 public: 3     bool hasPathSum(TreeNode* root, int sum) { 4         vector
     
       path; 5         path.reserve(100); 6         bool flag = false; 7         printPaths(root, path, 0, sum, flag); 8         return flag; 9     }10     void printPaths(TreeNode* node, vector
      
       & path, int pathlen, int& sum, bool& flag) {11         if (node == NULL) return;12         // append this node to the path array 13         path[pathlen++] = node->val;14         // path.push_back(node->val);15         // it's a leaf, so print the path that led to here  16         if (node->left == NULL && node->right == NULL) {17             printArray(path, pathlen, sum, flag);18             if (flag) return;19         }20         else {21             // otherwise try both subtrees  22             printPaths(node->left, path, pathlen, sum, flag);23             printPaths(node->right, path, pathlen, sum, flag);24             path.pop_back();25         }26     }27     void printArray(vector
       
         &ints, int len, int& sum, bool& flag) {28         int num = 0;29         for (int i = 0; i < len; i++) {30             // cout << ints[i] << " " ; 31             num += ints[i];32         }33         if (num == sum) flag = true;34         // cout << endl;35     }36 };
       
      
     

不过这种方法不好，空间开销大，效率还不高。在网上看到这种解法贴一下地址：