二叉树中和为某一值的路径

输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

二叉树遍历顺序有层次遍历，前中后序遍历。这里要找出二叉树的所有的路径里的节点的值的和为某个值的所有路径。前中后序遍历可以采用递归的方式进行但是这里感觉使用起来很困难，因为找的不是一次遍历。而是多条路径。从上到下分叉后就变为两条，但是没分叉之前的属于两条路径都应该包含的部分。所以自己通过建立一个栈，通过在必要的时候入栈和出栈，根据栈的元素得到每条路径，并根据元素的和判断是否符合条件。

function FindPath($root, $expectNumber)
{
    if($root==null){
        return [];
    }
    $stack = array($root);
    $result = array();
    while(count($stack)!=0){
        $topnode = end($stack);
        while ($topnode->left != null || $topnode->right!= null){
            if($topnode->left != null){
                $stack[] = $topnode->left;
                $p = $topnode->left;
                $topnode->left = null;
                $topnode = $p;
            }elseif ($topnode->right != null){
                $stack[] = $topnode->right;
                $p = $topnode->right;
                $topnode->right = null;
                $topnode = $p;
            }
        }
        $sum = 0;
        $sub_paths = array();
        foreach ($stack as $node){
            $sum += $node->val;
            $sub_paths[] = $node->val;
            if($sum>$expectNumber){
                break;
            }
        }
        if($sum==$expectNumber){
            $result[] = $sub_paths;
        }
        while($topnode->left == null && $topnode->right== null){
            array_pop($stack);
            if(count($stack)==0){
                return $result;
            }
            $topnode = end($stack);
        }
    }
    return result;
}

首先把树的根节点压入栈内，根据栈是否为空作为遍历结束条件。循环中每次都取栈顶元素。如果栈顶元素的左节点或者右节点不为空就进行压入，先判断左节点，保证每次访问路径是从左边的节点到右边的节点保存的，先判断右边和先判断左边没有本质区别。在压入栈后，将节点的左节点或者右节点赋值为null，是为了断开连接。防止出现死循环，在断开连接前都会先得到后面指向的节点。通过这层循环，就能得到一条路径了，因为只有叶子节点的左节点和右节点才会同时为null。中间部分就是访问当前栈内的元素得到本次的路径根据条件判断是否需要保存。路径保存后需要弹出栈，出栈条件是左右子树都为空，有两种情况，第一种就是叶子节点，叶子节点就是上面路径的最后一个节点，自然要弹出，第二种就是上面的while循环入栈前通过断开连接操作赋值为null造成的，这里是表明该节点的左右分叉的路径都已经输出了，这样自然也要弹出。这样最后栈顶节点就是没有分叉的路径还存在没有输出完的节点。总体就是利用栈和通过赋值null操作标记是否访问来得到每条路径并且根据路径的值的和来完成求解的。