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

题目描述

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

示例

输入：

{10,5,12,4,7},22

输出：

[[10,5,7],[10,12]]

分析

1. 用两个数组来存放路径，一个是存储当前搜索的路径$path[]，一个是存储了所有符合条件的路径$res[]。
2. 先将当前节点值$root->val放入数组$path[]。如果当前节点值等于期望值$expectNumber，且为叶子节点，则将当前路径保存到$res。
3. 如果当前节点值不等于$expectNumber，并且有左子树或右子树，则递归子节点。

代码

// 树节点
class TreeNode
{
    var $val;
    var $left = NULL;
    var $right = NULL;

    public function __construct($val){
        $this->val = $val;
    }
}

<?php

namespace app\index\controller;

class Index
{
  /**
   * 查找满足条件的路径
   *
   * @param object $root         节点
   * @param int    $expectNumber 期望值
   * @return array 二维数组
   */
    public function FindPath($root, $expectNumber)
    {
        $path = [];   // 满足条件的路径
        $res  = [];   // 满足条件的全部路径

        if (!$root) return $res;
        $this->TreeDFS($root, $expectNumber, $path, $res);
        return $res;
    }


    /**
     * 深度优先遍历
     *
     * @param object $root         当前节点
     * @param int    $expectNumber 期望值
     * @param array  $path         当前搜索路径
     * @param array  $res          所有符合条件的路径
     */
    public function TreeDFS($root, $expectNumber, $path, &$res)
    {
        $path[] = $root->val;  // 先保存当前节点值

        // 如果是到达子节点后路径总和等于期望值，则保存路径
        if ($root->val == $expectNumber && !$root->left && !$root->right) {
            $res[] = $path;
        }
        // 如果当前节点有左子树，则递归
        if ($root->left) {
            $this->TreeDFS($root->left, $expectNumber - $root->val, $path, $res);
        }
        // 如果当前节点有右子树，则递归
        if ($root->right) {
            $this->TreeDFS($root->right, $expectNumber - $root->val, $path, $res);
        }
    }
}

测试

<?php

namespace app\index\controller;

class Test
{

    /**
     * 测试
     */
    public function test()
    {
        // 构造树，#符号代表无节点：[1,-2,-3,1,3,-2,#,-1] 
        $root  = new TreeNode(1);
        $node1 = new TreeNode(-2);
        $node2 = new TreeNode(-3);
        $node3 = new TreeNode(1);
        $node4 = new TreeNode(3);
        $node5 = new TreeNode(-2);
        $node6 = new TreeNode(-1);

        $root->left   = $node1;
        $root->right  = $node2;
        $node1->left  = $node3;
        $node1->right = $node4;
        $node2->left  = $node5;
        $node3->left  = $node6;

        $all_path = $this->FindPath($root, -1);
        print_r($all_path);
    }
}