当前位置:首页 > PHP教程 > php高级应用 > 列表

php实现二叉树中和为某一值的路径方法

发布:smiling 来源: PHP粉丝网  添加日期:2021-10-31 20:01:25 浏览: 评论:0 

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

输入一颗二叉树的跟节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径,路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径,(注意: 在返回值的list中,数组长度大的数组靠前)

思路:

1、二叉树的前序遍历,中左右顺序

2、把目标值target传进去,target-=val

3、target为0并且left和right都为null,达到叶结点

4、函数外部两个数组,list数组存一条路径,listAll数组存所有路径

  1. FindPath(root,target) 
  2.  
  3.   if root==null return listAll 
  4.  
  5.   list[]=root.val 
  6.  
  7.   target-=root.val 
  8.  
  9.   if target==0 && root->left==null && root->right==null 
  10.  
  11.     listAll[]=list 
  12.  
  13.   FindPath(root->left,target) 
  14.  
  15.   FindPath(root->right,target) 
  16.  
  17.   //如果到了这条路径的跟结点,并没有达到目标,就删掉最后的结点,退回上一个结点 
  18.  
  19.   array_pop(list) 
  20.  
  21.   return listAll 
  22.  
  23. <?php 
  24.  
  25. class TreeNode{ 
  26.  
  27.   var $val
  28.  
  29.   var $left = NULL; 
  30.  
  31.   var $right = NULL; 
  32.  
  33.   function __construct($val){ 
  34.  
  35.     $this->val = $val
  36.  
  37.   }   
  38.  
  39.  
  40. function FindPath($root,$target
  41.  
  42.  
  43.     static $list=array(); 
  44.  
  45.     static $listAll=array(); 
  46.  
  47.     if($root==null){ 
  48.  
  49.         return $listAll
  50.  
  51.     }   
  52.  
  53.     $target-=$root->val; 
  54.  
  55.     $list[]=$root->val; 
  56.  
  57.     if($target==0 && $root->left==null && $root->right==null){ 
  58.  
  59.         $listAll[]=$list
  60.  
  61.     }   
  62.  
  63.     FindPath($root->left,$target); 
  64.  
  65.     FindPath($root->right,$target); 
  66.  
  67.     array_pop($list); 
  68.  
  69.     return $listAll
  70.  
  71. }
  72.  
  73. $node10=new TreeNode(10); 
  74.  
  75. $node5=new TreeNode(5); 
  76.  
  77. $node12=new TreeNode(12); 
  78.  
  79. $node4=new TreeNode(4); 
  80.  
  81. $node7=new TreeNode(7); 
  82.  
  83. $node10->left=$node5
  84.  
  85. $node10->right=$node12
  86.  
  87. $node5->left=$node4
  88.  
  89. $node5->left=$node7
  90.  
  91. $tree=$node10
  92.  
  93. $res=FindPath($tree,22); 
  94.  
  95. var_dump($res); 
  96.  
  97. <?php 
  98.  
  99. /*class TreeNode{ 
  100.  
  101.   var $val; 
  102.  
  103.   var $left = NULL; 
  104.  
  105.   var $right = NULL; 
  106.  
  107.   function __construct($val){ 
  108.  
  109.     $this->val = $val; 
  110.  
  111.   } 
  112.  
  113. }*/ 
  114.  
  115. function FindPath($root,$target
  116.  
  117.  
  118.   $list=array(); 
  119.  
  120.   $listAll=array(); 
  121.  
  122.   $res=dfs($root,$target,$list,$listAll); 
  123.  
  124.   return $res
  125.  
  126.  
  127. function dfs($root,$target,&$list,&$listAll
  128.  
  129. { 
  130.     if($root==null){ 
  131.  
  132.         return $listAll
  133.  
  134.     }   
  135.  
  136.     $target-=$root->val; 
  137.  
  138.     $list[]=$root->val; 
  139.  
  140.     if($target==0 && $root->left==null && $root->right==null){ 
  141.         $listAll[]=$list;
  142.     }   
  143.  
  144.     dfs($root->left,$target,$list,$listAll); 
  145.  
  146.     dfs($root->right,$target,$list,$listAll); 
  147.  
  148.     array_pop($list); 
  149.  
  150.     return $listAll;
  151. }

Tags: php二叉树 php某一值路径

分享到: