18、二叉搜索树的后序遍历序列及二叉树中和为某一值的路径

题目： 二叉搜索树的后序遍历序列

描述：
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。

<?php

function VerifySquenceOfBST($sequence)
{
    $size = count($sequence);if ($size==0) {return false;}
    $i = 0;
    while ($size--) {
        while ($sequence[$i++]<$sequence[$size]);
        while ($sequence[$i++]>$sequence[$size]);
         
        if ($i<$size) {
            return false;
        }
        $i=0;
    }
    return true;
}

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

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

<?php

/*class TreeNode{
    var $val;
    var $left = NULL;
    var $right = NULL;
    function __construct($val){
        $this->val = $val;
    }
}*/
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;
}