二叉树的所有路径

Question

给定一个二叉树，返回所有从根节点到叶子节点的路径。

说明: 叶子节点是指没有子节点的节点。

这道题目要求从根节点到叶子的路径，所以需要前序遍历，这样才方便让父节点指向孩子节点，找到对应的路径。

在这道题目中将第一次涉及到回溯，因为我们要把路径记录下来，需要回溯来回退一个路径再进入另一个路径。

var binaryTreePaths = function(root) {
    const path = [] //暂时存放路径
    const res = []  //结果
    digui(root,path,res)
    return res
};

var digui = function(root,path,res){     //前序遍历
    if(root===null) return  
    path.push(root.val)		
    if(root.left===null&&root.right===null){    //遍历到叶子结点  
        res.push(path)		//push进去的是path的引用
        console.log(res)
    }	    
    if(root.left!=null) {
        digui(root.left,path,res) 
        path.pop()			//回溯
    }
    if(root.right!=null) {
        digui(root.right,path,res) 
        path.pop()			//回溯
    }
}

这样出来的结果是不对的：

var binaryTreePaths = function(root) {
    const path = [] //暂时存放路径
    const res = []  //结果
    digui(root,path,res)
    return res
};

var digui = function(root,path,res){     //前序遍历
    if(root===null) return  
    path.push(root.val)		
    if(root.left===null&&root.right===null){    //遍历到叶子结点
        res.push([...path])   		//这样相当于构建了一个新数组
        //res.push(path)
        console.log(res)
    }	    
    if(root.left!=null) {
        digui(root.left,path,res) 
        path.pop()					//回溯
    }
    if(root.right!=null) {
        digui(root.right,path,res) 
        path.pop()					//回溯
    }
}

最后添一个转换成字符串的逻辑：

var binaryTreePaths = function(root) {
    const path = [] //暂时存放路径
    const res = []  //结果
    const ans = []
    digui(root,path,res)
    res.forEach((value)=>{      //转换成字符串
        let s = ""
        value.forEach((val,index)=>{
            s += val
            if(index!=value.length-1)
                s += "->"
        })
        ans.push(s)
        console.log(s)
    })
    return ans
};

var digui = function(root,path,res){     //前序遍历
    if(root===null) return  
    path.push(root.val)		
    if(root.left===null&&root.right===null){    //遍历到叶子结点
        res.push([...path])     //重要！！！
        console.log(res)
    }	    
    if(root.left!=null) {
        digui(root.left,path,res) 
        path.pop()              //回溯
    }
    if(root.right!=null) {
        digui(root.right,path,res) 
        path.pop()              //回溯
    }   
}

二叉树的所有路径 ​

二叉树的所有路径