php Realizes Path Method with Sum as a Value in Binary Tree
- 2021-11-10 08:59:37
- OfStack
A path in a 2-tree where the sum is a value of 1:
Enter a heel node of a 2-tree and an integer, and print out all paths where the sum of node values in the 2-tree is the input integer. The path is defined as a path from the root node of the tree down 1 to the node through which the leaf node passes to form 1 path. (Note: In the list of the return value, the array with large array length comes first.)
Thoughts:
Pre-order traversal of 1, 2-tree, middle left and right order
2. Pass in the target value target, target-=val
3. target is 0 and left and right are null, reaching the leaf node
4. Two arrays outside the function, list array stores one path and listAll array stores all paths
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)
// If you reach the following node of this path and fail to achieve the goal, delete the last node and return to the upper node 1 Node
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;
}
The above is the content of all examples of the code, you can test 1, thank you for the support of this site.