二叉樹中和為某一值的路徑：
輸入一顆二叉樹的跟節點和一個整數，打印出二叉樹中結點值的和為輸入整數的所有路徑。路徑定義為從樹的根結點開始往下一直到葉結點所經過的結點形成一條路徑。(注意: 在返回值的list中，數組長度大的數組靠前)
思路：
1、二叉樹的前序遍歷，中左右順序
2、把目標值target傳進去，target-=val
3、target為0并且left和right都為null，達到葉結點
4、函數外部兩個數組，list數組存一條路徑，listAll數組存所有路徑
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) //如果到了這條路徑的跟結點，并沒有達到目標，就刪掉最后的結點，退回上一個結點 array_pop(list) return listAll
<?phpclass 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;}以上就是本次內容的全部實例代碼，大家可以本次測試一下，感謝大家對VeVb武林網的支持。
新聞熱點
疑難解答
圖片精選
