[leetcode]二叉树的前序遍历

题目描述

给定一个二叉树,返回它的前序遍历。
示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [1,2,3]

算法实现

前序遍历首先访问根节点,然后遍历左子树,最后遍历右子树

递归版(php)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
* Definition for a binary tree node.
* class TreeNode {
* public $val = null;
* public $left = null;
* public $right = null;
* function __construct($value) { $this->val = $value; }
* }
*/
class Solution {
public $result = [];
/**
* @param TreeNode $root
* @return Integer[]
*/
function preorderTraversal($root) {
$this->doTraverse($root);
return $this->result;
}
function doTraverse($node)
if($node==null){
return;
}
array_push($this->result,$node->val);
if($node->left!=null) $this->doTraverse($node->left);
if($node->right!=null) $this->doTraverse($node->right);
}
}

迭代版(php)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
* Definition for a binary tree node.
* class TreeNode {
* public $val = null;
* public $left = null;
* public $right = null;
* function __construct($value) { $this->val = $value; }
* }
*/
class Solution {
public $result = [];
public $stack = [];
/**
* @param TreeNode $root
* @return Integer[]
*/
function preorderTraversal($root) {
if($root==null){
return [];
}
$this->stack[] = $root;
do{

$node = array_pop($this->stack);
$this->result[] = $node->val;

if($node->right!=null){
$this->stack[] = $node->right;
}
if($node->left!=null){
$this->stack[] = $node->left;
}

}while(!empty($this->stack));

return $this->result;
}
}

参考

二叉树的前序遍历