深度优先遍历
先序遍历：根->左->右
中序遍历：左->根->右
后序遍历：左->右->根
先序遍历
节点定义
class TreeNode { public $val = null; public $left = null; public $right = null; function __construct($value) { $this->val = $value; }}预览思路
非递归先序遍历，使用栈结构
class Solution { /**
* @param TreeNode $root
* @return Integer[]
*/ 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 { /**
* @param TreeNode $root
* @return Integer[]
*/ 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; /**
* @param TreeNode $root
* @return Integer[]
*/ 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; }
/**
* @param TreeNode $root
* @return TreeNode
*/ 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;$ival;//如果有子节点，那么就入队 if($tmp->left != null){ array_push($list, $tmp->left); } if($tmp->right != null){ array_push($list, $tmp->right); } } $res[] = $tmp_arr; } return $res; }}预览思路
层次遍历使用一个队列保存每层的节点，遍历这次的所有节点，这个过程中取出下层的子节点入队。如果队列不为空，继续遍历。利用了队列先进先出的性质。
评论 (0)