代码随想录算法训练营第十一天 | leetcode：二叉树理论基础,递归遍历,迭代遍历
0 / 0 / 创建于 1年前 /
_zzh 的个人博客
二叉树理论知识
二叉树种类
满二叉树：
如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。
完全二叉树
在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（h从1开始），则该层包含 1~ 2^(h-1) 个节点。(最底层节点是连续的)
二叉搜索树
前面介绍的树，都没有数值的，而二叉搜索树是有数值的了，二叉搜索树是一个有序树。
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 它的左、右子树也分别为二叉排序树
平衡二叉搜索树
平衡二叉搜索树：又被称为AVL（Adelson-Velsky and Landis）树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
二叉树遍历方式
二叉树主要有两种遍历方式：
- 深度优先遍历：先往深走，遇到叶子节点再往回走。
- 前序遍历（递归法，迭代法）
- 中序遍历（递归法，迭代法）
- 后序遍历（递归法，迭代法）
- 广度优先遍历：一层一层的去遍历。
- 层次遍历（迭代法）
二叉树定义
class TreeNode {
public $val = null;
public $left = null;
public $right = null;
function __construct($val = 0, $left = null, $right = null) {
$this->val = $val;
$this->left = $left;
$this->right = $right;
}
}
// 测试例程
// $root = new TreeNode(0);
// $root->left = new TreeNode(null);
// $root->right = new TreeNode(2);
// $root->right->left = new TreeNode(3);
// print_r($root);
// $test = new Solution();
// $res = $test->preorderTraversal($root);
// print_r($res);Problem: 144. 二叉树的前序遍历
解题方法
1. 递归法
class Solution {
/**
* @param TreeNode $root
* @return Integer[]
*/
function preorderTraversal($root) {
$res = [];
$this->treeLoop($root, $res);
return $res;
}
function treeLoop($cur, &$res){
if($cur == null) return;
$res[] = $cur->val;
$this->treeLoop($cur->left, $res);
$this->treeLoop($cur->right, $res);
}
}2. 迭代法
class Solution {
/**
* @param TreeNode $root
* @return Integer[]
*/
function preorderTraversal($root) {
/** 实际不符合深度优先遍历顺序，更像层级遍历顺序 */
$stack = new SplStack();
$res = [];
if($root == null) return $res;
$stack->push($root);
//按中右左依次一层一层入栈数据 出栈按中左右
while(!$stack->isEmpty()){
$node = $stack->top();
$res[] = $node->val;
$stack->pop();
if($node->right) $stack->push($node->right);
if($node->left) $stack->push($node->left);
}
return $res;
}
}Problem: 145. 二叉树的后序遍历
解题方法
1. 递归法
class Solution {
/**
* @param TreeNode $root
* @return Integer[]
*/
function postorderTraversal($root) {
$res = [];
$this->treeLoop($root, $res);
return $res;
}
function treeLoop($cur, &$res){
if($cur == null) return;
$this->treeLoop($cur->left, $res);
$this->treeLoop($cur->right, $res);
$res[] = $cur->val;
}
}2. 迭代法
class Solution {
/**
* @param TreeNode $root
* @return Integer[]
*/
function postorderTraversal($root) {
/** 实际不符合深度优先遍历顺序，更像层级遍历顺序 */
$stack = new SplStack();
$res = [];
if($root == null) return $res;
$stack->push($root);
//按中左右依次一层一层入栈数据 出栈按中右左
while(!$stack->isEmpty()){
$node = $stack->top();
$res[] = $node->val;
$stack->pop();
if($node->left) $stack->push($node->left);
if($node->right) $stack->push($node->right);
}
//最后反转数组，就变成左右中后序了
return array_reverse($res);
}
}Problem: 94. 二叉树的中序遍历
解题方法
1. 递归法
class Solution {
/**
* @param TreeNode $root
* @return Integer[]
*/
function inorderTraversal($root) {
$res = [];
$this->treeLoop($root, $res);
return $res;
}
function treeLoop($cur, &$res){
if($cur == null) return;
$this->treeLoop($cur->left, $res);
$res[] = $cur->val;
$this->treeLoop($cur->right, $res);
}
}2. 迭代法
class Solution {
/**
* @param TreeNode $root
* @return Integer[]
*/
function inorderTraversal($root) {
$res = [];
if($root == null) return $res;
$stack = new SplStack();
$cur = $root;
while($cur != null || !$stack->isEmpty()){
if($cur != null){
//一直向左，直到指针的左孩子为空
$stack->push($cur);
$cur = $cur->left;
}else{
//左孩子为空，弹出栈顶元素
$cur = $stack->top();
$stack->pop();
$res[] = $cur->val;
//查找当前弹出栈顶的右孩子
$cur = $cur->right;
}
}
return $res;
}
}本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号