題干

輸入一棵二叉樹和一個整數(shù)，打印出二叉樹中節(jié)點值的和為輸入整數(shù)的所有路徑。從樹的根節(jié)點開始往下一直到葉子節(jié)點所經(jīng)過的節(jié)點形成一條路徑。二叉樹節(jié)點的定義如下

class TreeNode{
    int val;
    TreeNode left;
    TreeNode right;
}

解題思路

使用二叉樹的前序遍歷方式進行遍歷，使用棧記錄每個遍歷到的節(jié)點，并記錄當(dāng)前遍歷當(dāng)節(jié)點當(dāng)累加和，當(dāng)?shù)竭_葉子節(jié)點時，判斷累計和是否等于要求的值，如果是，則打印當(dāng)前棧中的所有元素，如果不等于，則執(zhí)行剛才的逆操作，使用類似流程直到遍歷完所有節(jié)點為止。

代碼實現(xiàn)

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