题干
输入一棵二叉树和一个整数，打印出二叉树中节点值的和为输入整数的所有路径。从树的根节点开始往下一直到叶子节点所经过的节点形成一条路径。二叉树节点的定义如下
class TreeNode{
int val;
TreeNode left;
TreeNode right;
}
解题思路
使用二叉树的前序遍历方式进行遍历，使用栈记录每个遍历到的节点，并记录当前遍历当节点当累加和，当到达叶子节点时，判断累计和是否等于要求的值，如果是，则打印当前栈中的所有元素，如果不等于，则执行刚才的逆操作，使用类似流程直到遍历完所有节点为止。
代码实现
<?php
class TreeNode
{
private $val;
private $left;
private $right;
public function __set($name, $value)
{
$this->$name = $value;
}
public function __get($name)
{
return $this->$name;
}
}
function getTree()
{
$node1 = new TreeNode();
$node1->val = 10;
$node2 = new TreeNode();
$node2->val = 5;
$node3 = new TreeNode();
$node3->val = 12;
$node1->left = $node2;
$node1->right = $node3;
$node4 = new TreeNode();
$node4->val = 4;
$node5 = new TreeNode();
$node5->val = 7;
$node2->left = $node4;
$node2->right = $node5;
return $node1;
}
function getPath($tree, $target)
{
if (empty($tree)) {
return null;
}
$stack = [];
$sum = 0;
doGetPath($tree, $target, $stack, $sum);
}
function doGetPath($tree, $target, &$stack, &$sum)
{
$sum += $tree->val;
array_push($stack, $tree);
if ($tree->left == null && $tree->right == null) {
if ($sum == $target) {
foreach ($stack as $item) {
echo $item->val.' ';
}
echo PHP_EOL;
}
}
if ($tree->left) {
doGetPath($tree->left, $target, $stack, $sum);
}
if ($tree->right) {
doGetPath($tree->right, $target, $stack, $sum);
}
$sum -= $tree->val;
array_pop($stack);
}
getPath(getTree(), 22);
