Leetcode-257：二叉树的所有路径

257. 二叉树的所有路径
题目描述：
// 给你一个二叉树的根节点 root ，按 任意顺序 ，返回所有从根节点到叶子节点的路径。
// 叶子节点 是指没有子节点的节点。

对于这道题很容易就可以看出来是个遍历问题的衍生，而且根据题目要求是输出路径，所以我们可以联想到使用先序遍历（根左右的顺序来进行路径打印）。
需要处理的是每个节点的路径的保存要确保不对其它的节点路径造成影响，所以使用递归的话在其回溯过程会需要处理那些多余的叶节点。

如在上述图示中，红色箭头表示深度向下打印path的路径，灰色虚线箭头表示到达叶节点之后的回溯。在我们完成A->B->D路径保存后，需要回溯到B重新进行访问，所以我们在递归过程中需要一个变量记录当前节点处的path（节点的之后节点处理不能影响这个path值），需要维护一个string的vector。为了实现回溯path不能是引用形参。所以我们的代码如下所示。

// 先序递归解决（O(N^2),O(N^2)）
class Solution {
public:
	//思考这里为什么path不使用引用
    void binaryTree(TreeNode* root,vector &vs,string path){
        // 打印当前遍历节点
        path += to_string(root->val);
        // 当前节点是叶子节点就说明一条路径处理完
        if(root->left == nullptr && root->right == nullptr){
            vs.push_back(path);
            return;
        }
        // 当前不是叶子节点，分别处理左右子节点
        if(root->left) binaryTree(root->left,vs,path+"->");
        if(root->right) binaryTree(root->right,vs,path+"->");
    }
    vector binaryTreePaths(TreeNode* root) {
        // 初始化辅助数据
        vector res;
        string path;
        // 节点为空直接输出
        if(root == nullptr) return res;
        // 调用递归打印
        binaryTree(root,res,path);
        return res;
    }
};

既然是遍历相关，我们也可以考虑使用层次遍历入手，会发现通过记录更新每个节点的path队列，就可以实现叶子结点的path输出。
// 广度优先（O(N^2),O(N2)）
// 该方法本质上就是维护一个与遍历节点队列相对应的遍历节点所拥有的路径队列
如对于层序为123的树，其队列改变状态分别为1–>2–>2,3–>3和“1”–>“1->2,1->3”

class Solution {
public:
    vector binaryTreePaths(TreeNode* root) {
        // 初始化结果向量resPath、
        // 保存每个结点的当前路径的quePath，已经节点访问队列queNode
        vector resPath;
        if(root == nullptr) return resPath;
        queue queNode;
        queue quePath;
        // 首元素入队，首元素组成的path入队
        queNode.push(root);
        quePath.push(to_string(root->val));
        
        while(!queNode.empty()){
            // 取出两个队首元素分别用于广度遍历和路径更新
            TreeNode* node = queNode.front();
            string path = quePath.front();
            // 弹出队首元素
            queNode.pop();
            quePath.pop();

            //如果已经是叶子节点，那么保存此路径到resParh 
            if(!node->right && !node->left){
                resPath.push_back(path);
            }
            // 否则，继续访问队首元素的子节点并更新路径队列的值
            else{
             if(node->left){
                queNode.push(node->left);
                quePath.push(path+"->"+to_string(node->left->val));
            } 
            if(node->right){
                queNode.push(node->right);
                quePath.push(path+"->"+to_string(node->right->val));
            }   
            }
        }
        return resPath;
    }
};