到达二叉树目标节点的完整路径

有一颗二叉树，写代码找出来从根节点到flag节点的最短路径并打印出来，flag节点有多个。比如下图这个树中的6和14是flag节点，请写代码打印8、3、6 和 8、10、14两个路径

pesudo code :

//广度优先
findPathInNode(root,target)
    make a queue
    push [root,path] into queue

    while queue is not empty
         pop pairs
         node = pairs[0]
         path = pairs[1]

         if node->left==target
            return path[]=target
         elseif node->right==target
            return path[]=target
         else
            push [left,path[]=left] into queue
            push [right,path[]=right] into queue

         return []

//深度优先
findPathInNode(root,target)
    findPathIn(root,target,rootPath=[root->val])
    if node has no child and val not equal to target
        return false

        if node->val==target
            return rootPath[]=node->val
        else 
            res1 = findPathIn(left,target,rootPath[]=left->val)
            res2 = findPathIn(right,target,rootPath[]=right->val)

            if res1
                return res1

            if res2
                return res2

            return []

//二叉搜索树的情况
node = root
res=[]
while node is not leaf
    if node==t
        put node val into res
        return res
    if node>t
        put node into res
        node=node left
        continue
    if node<t
        put node into res
        node = node right
        continue

return []

go的bfs实现 , 参考了之前写的perfect squares

复盘: 思维定式 , 想当然的认为只能把node推入队列 , 不过想到了存储parent到节点中, 其实也是可以解决的 , 最后是参考之前做的perfect squares 把pairs [node , path ]推入

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
    RootPath []int
}

//bfs
func findPathInNode(root *TreeNode,target int ) []int{
    q:=[]*TreeNode{}
    root.RootPath = []int{root.Val}
    q=append(q,root)

    for len(q)!=0 {
        node:=q[0]
        q=q[1:]

        if node.Left.Val==target {
            return append(node.RootPath,target)
        } else if node.Right.Val==target {
            return append(node.RootPath,target)
        } else {
            node.Left.RootPath = append(node.RootPath,node.Left.Val)
            q=append(q,node.Left)

            node.Right.RootPath = append(node.RootPath,node.Right.Val)
            q=append(q,node.Right)
        }

    }
    return []int{}
}

本作品采用《CC 协议》，转载必须注明作者和本文链接