<?php 
/** 
 * 二叉树中和为某一值的路径
 * 输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
 * 思路：先序遍历
 */


class TreeNode{
    public $val;
    public $left = NULL;
    public $right = NULL;
    public function __construct($val){
        $this->val = $val;
    }
}



function FindPath($root, $expectNumber)
{
    if ($root == null) {
    	return '';
    }
    $path = [];
    $curSum = 0;
    FindPathDetail($root, $expectNumber, $path, $curSum);
}


function FindPathDetail($root, $expectNumber, $path, $curSum)
{
	if ($root != null) {
		array_push($path, $root->val);
		$curSum += $root->val;
		if ($expectNumber == $curSum) {
			printPath($path);
		}

		FindPathDetail($root->left, $expectNumber, $path, $curSum);
		FindPathDetail($root->right, $expectNumber, $path, $curSum);

		// 回到父节点之前，需要删除当前节点
		$curSum -= $root->val;
		array_pop($path);
	}
}

function printPath($path)
{
	foreach ($path as $key => $value) {
		echo $value.' ';
	}
	echo '<br />';
}

$node = new TreeNode(10);
$node->left = new TreeNode(5);
$node->right = new TreeNode(12);
$node->left->left = new TreeNode(4);
$node->left->right = new TreeNode(7);

$num = 22;
FindPath($node, $num);