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

输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径，路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径，(注意: 在返回值的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.  
41. function FindPath($root,$target) 
42.  
43. { 
44.  
45.     static $list=array(); 
46.  
47.     static $listAll=array(); 
48.  
49.     if($root==null){ 
50.  
51.         return $listAll; 
52.  
53.     }   
54.  
55.     $target-=$root->val; 
56.  
57.     $list[]=$root->val; 
58.  
59.     if($target==0 && $root->left==null && $root->right==null){ 
60.  
61.         $listAll[]=$list; 
62.  
63.     }   
64.  
65.     FindPath($root->left,$target); 
66.  
67.     FindPath($root->right,$target); 
68.  
69.     array_pop($list); 
70.  
71.     return $listAll; 
72.  
73. }
74.  
75. $node10=new TreeNode(10); 
76.  
77. $node5=new TreeNode(5); 
78.  
79. $node12=new TreeNode(12); 
80.  
81. $node4=new TreeNode(4); 
82.  
83. $node7=new TreeNode(7); 
84.  
85. $node10->left=$node5; 
86.  
87. $node10->right=$node12; 
88.  
89. $node5->left=$node4; 
90.  
91. $node5->left=$node7; 
92.  
93. $tree=$node10; 
94.  
95. $res=FindPath($tree,22); 
96.  
97. var_dump($res); 
98.  
99. <?php 
100.  
101. /*class TreeNode{ 
102.  
103.   var $val; 
104.  
105.   var $left = NULL; 
106.  
107.   var $right = NULL; 
108.  
109.   function __construct($val){ 
110.  
111.     $this->val = $val; 
112.  
113.   } 
114.  
115. }*/ 
116.  
117. function FindPath($root,$target) 
118.  
119. { 
120.  
121.   $list=array(); 
122.  
123.   $listAll=array(); 
124.  
125.   $res=dfs($root,$target,$list,$listAll); 
126.  
127.   return $res; 
128.  
129. } 
130.  
131. function dfs($root,$target,&$list,&$listAll) 
132.  
133. { 
134.     if($root==null){ 
135.  
136.         return $listAll; 
137.  
138.     }   
139.  
140.     $target-=$root->val; 
141.  
142.     $list[]=$root->val; 
143.  
144.     if($target==0 && $root->left==null && $root->right==null){ 
145.         $listAll[]=$list;
146.     }   
147.  
148.     dfs($root->left,$target,$list,$listAll); 
149.  
150.     dfs($root->right,$target,$list,$listAll); 
151.  
152.     array_pop($list); 
153.  
154.     return $listAll;
155. }

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

分享到：