深度优先遍历
先序遍历：根->左->右
中序遍历：左->根->右
后序遍历：左->右->根
先序遍历
节点定义
class TreeNode {
public $val = null;
public $left = null;
public $right = null;
function __construct($value) { $this->val = $value; }
}
思路
非递归先序遍历，使用栈结构
class Solution {
function preorderTraversal($root) {
if($root == null){
return [];
}
$res = [];
$this->preorder($root, $res);
return $res;
}
function preorder($root, &$res){
$stack = [];
//先向栈中推入根节点
array_push($stack, $root);
//判断栈中是否有元素，如果有进行遍历；没有元素，结束遍历。
while(!empty($stack)){
//取出栈中的一个元素
$root = array_pop($stack);
//先序遍历，先根节点
$res[] = $root->val;
//下面先右节点入栈，这样出栈时，先处理左节点
if($root->right != null){
array_push($stack, $root->right);
}
if($root->left != null){
array_push($stack, $root->left);
}
}
}
}
中序遍历
中序遍历的递归实现
class Solution {
function inorderTraversal($root) {
if($root == null){
return [];
}
$res = [];
$this->inorder($root, $res);
return $res;
}
function inorder($root, &$res){
if($root == null){
return ;
}
//先把左子树存入结果
if($root->left != null){
$this->inorder($root->left, $res);
}
$res[] = $root->val;
if($root->right != null){
$this->inorder($root->right, $res);
}
}
}
后序遍历
class Solution {
public $res;
function postorderTraversal($root) {
if($root === null){
return [];
}
$this->_postOrder($root);
return $this->res;
}
function _postOrder($root){
if($root === null){
return ;
}
$this->_postOrder($root->left);
$this->_postOrder($root->right);
$this->res[] = $root->val;
}
}
层次遍历
层次遍历：每层从左向右一次遍历每一层。
class Solution {
function getHeight($root){
if($root == null){
return 0;
}
$left_height = $this->getHeight($root->left);
$right_height = $this->getHeight($root->right);
return $left_height > $right_height ? $left_height +1 : $right_height +1;
}
function levelOrder($root) {
$list = []; //list是队列
$res = []; //最终结果
if($root == null){
return [];
}
//先把根节点入队
array_push($list, $root);
//如果队列不为空，说明没有遍历完
while(!empty($list)){
$size = count($list);
$tmp_arr = [];
//根据每层入队的节点数，进行循环
for($i=0;$i<$size;$i++){
//队列出队一个元素，在for中把这层元素都过一遍
$tmp = array_shift($list);
//保存层次遍历的中间结果
$tmp_arr[] = $tmp->val;
//如果有子节点，那么就入队
if($tmp->left != null){
array_push($list, $tmp->left);
}
if($tmp->right != null){
array_push($list, $tmp->right);
}
}
$res[] = $tmp_arr;
}
return $res;
}
}
思路
层次遍历使用一个队列保存每层的节点，遍历这次的所有节点，这个过程中取出下层的子节点入队。如果队列不为空，继续遍历。利用了队列先进先出的性质。
