php實現(xiàn)二叉樹中和為某一值的路徑方法

更新時間：2018年10月14日 14:50:07 投稿：laozhang

在本篇文章中我們給大家分享了php實現(xiàn)二叉樹中和為某一值的路徑方法，有需要的朋友們可以參考下。

二叉樹中和為某一值的路徑：

輸入一顆二叉樹的跟節(jié)點和一個整數(shù)，打印出二叉樹中結(jié)點值的和為輸入整數(shù)的所有路徑。路徑定義為從樹的根結(jié)點開始往下一直到葉結(jié)點所經(jīng)過的結(jié)點形成一條路徑。(注意: 在返回值的list中，數(shù)組長度大的數(shù)組靠前)

思路：

1、二叉樹的前序遍歷，中左右順序

2、把目標值target傳進去，target-=val

3、target為0并且left和right都為null，達到葉結(jié)點

4、函數(shù)外部兩個數(shù)組，list數(shù)組存一條路徑，listAll數(shù)組存所有路徑

FindPath(root,target)

  if root==null return listAll

  list[]=root.val

  target-=root.val

  if target==0 && root->left==null && root->right==null

    listAll[]=list

  FindPath(root->left,target)

  FindPath(root->right,target)

  //如果到了這條路徑的跟結(jié)點，并沒有達到目標，就刪掉最后的結(jié)點，退回上一個結(jié)點

  array_pop(list)

  return listAll

<?php

class TreeNode{

  var $val;

  var $left = NULL;

  var $right = NULL;

  function __construct($val){

    $this->val = $val;

  }  

}

 

function FindPath($root,$target)

{

    static $list=array();

    static $listAll=array();

    if($root==null){

        return $listAll;

    }  

    $target-=$root->val;

    $list[]=$root->val;

    if($target==0 && $root->left==null && $root->right==null){

        $listAll[]=$list;

    }  

    FindPath($root->left,$target);

    FindPath($root->right,$target);

    array_pop($list);

    return $listAll;

}

 

$node10=new TreeNode(10);

$node5=new TreeNode(5);

$node12=new TreeNode(12);

$node4=new TreeNode(4);

$node7=new TreeNode(7);

 

$node10->left=$node5;

$node10->right=$node12;

$node5->left=$node4;

$node5->left=$node7;

 

$tree=$node10;

 

$res=FindPath($tree,22);

var_dump($res);

<?php

/*class TreeNode{

  var $val;

  var $left = NULL;

  var $right = NULL;

  function __construct($val){

    $this->val = $val;

  }

}*/

function FindPath($root,$target)

{

  $list=array();

  $listAll=array();

  $res=dfs($root,$target,$list,$listAll);

  return $res;

}

 

function dfs($root,$target,&$list,&$listAll)

{

 

    if($root==null){

        return $listAll;

    }  

    $target-=$root->val;

    $list[]=$root->val;

    if($target==0 && $root->left==null && $root->right==null){

         

        $listAll[]=$list;

    }  

    dfs($root->left,$target,$list,$listAll);

    dfs($root->right,$target,$list,$listAll);

    array_pop($list);

    return $listAll;

}

以上就是本次內(nèi)容的全部實例代碼，大家可以本次測試一下，感謝大家對腳本之家的支持。

您可能感興趣的文章: