---答题基础知识储备---

树操作中“广度优先遍历”与“深度优先遍历”的区别：

1. 二叉树深度优先遍历非递归的通用做法是使用栈，广度优先遍历非递归的通用做法是使用线性表。

2. 树的深度优先遍历原理是对每一个可能的分支路径深入到不能在深入为止，而且每个节点只访问一次，需要特别注意的是，二叉树的深度优先遍历可以细分为先序遍历、中序遍历和后序遍历三种；
   树的广度优先遍历又叫做层次优先遍历，原理是对树由上至下逐层进行访问，在每一层中由左至右，访问完一层再访问下一层，直到访问完所有节点。

3. 深度优先搜索算法：操作栈中不保留树的全部节点，只保留当前路径上的节点，占用空间小；可以回溯(通过入栈、出栈操作)；运行速度较慢；

   广度优先搜索算法：操作线性表中保存全部节点，占用空间较大，在遇到广度优先的问题时，注意考虑内存溢出和节省内存空间的问题；不可以回溯；运行速度较快；
   

------

题目：

输入一个整数和一棵二元树，从树的根节点开始向下访问，一直到叶节点所经过的所有节点形成一条路径；要求打印出和与输入整数相等的所有路径。

例如，输入整数22和如下二元树：

    10

   / \

  5  12

 / \

4   7

则结果会打印出两条路径：10,5,7和10,12

二元树节点的数据结构定义为：

struct BinaryTreeNode // a node in the binary tree  
{  
    int m_nValue; // value of node  
    BinaryTreeNode *m_pLeft; // left child of node  
    BinaryTreeNode *m_pRight; // right child of node  
};

答题分析：

使用递归方式对二元树进行深度优先前序遍历，使用堆栈保存当前经过的路径；

1. 设置一个变量sum保存当前路径经过节点值的和

2. 对于非叶子节点，将当前节点值加入sum，继续向下遍历

3. 对于叶子节点，将当前节点值加入sum，并比较sum和预设值

   如果sum==预设值，返回true及当前压入栈的路径，删除当前节点

   如果sum!=预设值，删除当前节点，sum值减去当前节点值，向上回溯，继续遍历

4. 对于被删除的节点，直接返回false

解答：

代码实现：

struct TreeNode{
    int data;
    TreeNode * left;
    TreeNode * right;
};
void printPaths(TreeNode * root,int sum){
    int path[MAX_HEIGHT];
    helper(root,sum,path,0);
}
void helper(TreeNode * root,int sum,int path[],int top){
     path[top++] = root.data;
     sum -= root.data;
     if(root->left==NULL&&root->right==NULL){
         // 叶子节点
         if(sum==0) printPath(path,top);
     }else{
         // 非叶子节点  继续向下遍历
         if(root->left!=NULL) helper(root->left,sum,path,top);
         if(root->right!=NULL) helper(root->right,sum,path,top);
     }
     top--;// 回溯
     sum += root.data;
}