根结点到所有叶子结点的路径（java、C++）

java（针对树的编码），C++（针对二叉树的编码）

思路一：

采用深度优先遍历（java Stack，C++ vector）的方式，每当遇到叶子节点，此刻栈里面的内容就是该叶子节点对应的一条路径

java
注意到达叶子节点过后，得到了这条路径，需要把叶子节点立马出栈，注意出栈代码写的位置
可以写在出栈位置1，或者写在出栈位置2
参考：https://blog.csdn.net/leixingbang1989/article/details/40587405/

class node {
private String text;
private List<node>childList;
}

public class IteratorNodeTool {
    Map<String,List> pathMap=new HashMap();//记录所有从根节点到叶子结点的路径
    private void print(List lst)//打印出路径
    {
        Iterator it=lst.iterator();
        while(it.hasNext())
        {
            node n=(node)it.next();
            System.out.print(n.text+"-");
        }
        System.out.println();
    }
    public void iteratorNode(node n,Stack<node> pathstack)
    {
          pathstack.push(n);//入栈
          List childlist=n.childList;
          if(childlist==null)//没有孩子 说明是叶子结点
          {
              List lst=new ArrayList();
              Iterator stackIt=pathstack.iterator();
              while(stackIt.hasNext())
              {
                  lst.add(stackIt.next());
                  
              }
              print(lst);//打印路径
             pathMap.put(n.getText(), lst);//保存路径信息
            return;
          }else
          {
              Iterator it=childlist.iterator();
              while(it.hasNext())
              {
                   node child=(node)it.next();
                   iteratorNode(child,pathstack);//深度优先 进入递归
                   pathstack.pop();//回溯时候出栈,出栈位置1
              }
              
          }
　　　　　　//pathstack.pop();//出栈位置2
          
    }
    public static void main(String[] args) {
        Stack <node>pathstack=new Stack();
        node n=node.getInitNode();
        IteratorNodeTool  tool=new IteratorNodeTool();
        tool.iteratorNode(n, pathstack);
    }
 
}

C++
参考：https://blog.csdn.net/zzIymt/article/details/50816059

void LeavesPath(TreeNode* root, vector<int> &path){//引用vector
    if (root == NULL) return;
    path.push_back(root->val);
    if (root->left == NULL&&root->right == NULL){
        for (int i = 0; i < path.size(); i++){
            cout << path[i] << "  ";
        }
        cout << endl;
    }
    else
    {
        LeavesPath(root->left, path);
        LeavesPath(root->right, path);
    }
    path.pop_back();//关键
}

或者（出栈代码位置不同）

void LeavesPath(TreeNode* root, vector<int> &path){//引用vector
    if (root == NULL) return;
    path.push_back(root->val);
    if (root->left == NULL&&root->right == NULL){
        for (int i = 0; i < path.size(); i++){
            cout << path[i] << "  ";
        }
        cout << endl;
    }
    else
    {
        LeavesPath(root->left, path);
        path.pop_back();//关键
        LeavesPath(root->right, path);
        path.pop_back();//关键
    }
}

// 测试代码
 vector<int> path;
LeavesPath(&n0, path);//n0为自己建造的树的根结点

思路二：数组

少了思路一中的出栈操作，因为数组在指定索引赋值可以直接覆盖原有的值，并且用len记录了当前节点的深度（根节点深度为0）

void LeavesPath2(TreeNode* root, int* path,int len){
    if (root == NULL) return;
    path[len++] = root->val;
    if (root->left == NULL&&root->right == NULL){
        for (int i = 0; i < len; i++){
            cout << path[i] << "  ";
        }
        cout << endl;
    }
    else
    {
        LeavesPath2(root->left, path, len);
        LeavesPath2(root->right, path, len);
    }
}

//测试代码
int path2[20] = { 0 };
 LeavesPath2(&n0, path2, 0); //n0为自己建造的树的根结点

(引用)数组+引用长度

注意这儿参数的len是一个引用，当递归的时候，其实操作的都是同一个对象。

而思路二中的len参数定义为int len，是一个局部变量

void LeavesPath3(TreeNode* root, int* &path, int& len){//int* &path替换成int*path也可以
    if (root == NULL) return;
    path[len++] = root->val;
    if (root->left == NULL&&root->right == NULL){
        for (int i = 0; i < len; i++){
            cout << path[i] << "  ";
        }
        cout << endl;
    }
    else
    {
        LeavesPath3(root->left, path, len);
        LeavesPath3(root->right, path, len);
    }
    --len;//这步操作与版本一中pop_back目的一样。
}

//测试程序

        int path2[20] = { 0 };
        int len = 0;
        int *path3 = path2;
        LeavesPath3(&n0, path3, len);//n0为自己建造的树的根结点