《剑指Offer》-34.二叉树中和为某一值的路径

题干

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

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);