代码随想录算法训练营第十一天 | leetcode:二叉树理论基础,递归遍历,迭代遍历

二叉树理论知识

二叉树种类

满二叉树

如果一棵二叉树只有度为0的结点和度为2的结点,并且度为0的结点在同一层上,则这棵二叉树为满二叉树。

完全二叉树

在完全二叉树中,除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层(h从1开始),则该层包含 1~ 2^(h-1) 个节点。(最底层节点是连续的)

代码随想录算法训练营第十一天 | leetcode:二叉树理论基础,递归遍历,迭代遍历

二叉搜索树

前面介绍的树,都没有数值的,而二叉搜索树是有数值的了,二叉搜索树是一个有序树

  • 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
  • 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
  • 它的左、右子树也分别为二叉排序树

代码随想录算法训练营第十一天 | leetcode:二叉树理论基础,递归遍历,迭代遍历

平衡二叉搜索树

平衡二叉搜索树:又被称为AVL(Adelson-Velsky and Landis)树,且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

代码随想录算法训练营第十一天 | leetcode:二叉树理论基础,递归遍历,迭代遍历

二叉树遍历方式

二叉树主要有两种遍历方式:

  • 深度优先遍历:先往深走,遇到叶子节点再往回走。
    • 前序遍历(递归法,迭代法)
    • 中序遍历(递归法,迭代法)
    • 后序遍历(递归法,迭代法)
  • 广度优先遍历:一层一层的去遍历。
    • 层次遍历(迭代法)

二叉树定义

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 协议》,转载必须注明作者和本文链接
《L01 基础入门》
我们将带你从零开发一个项目并部署到线上,本课程教授 Web 开发中专业、实用的技能,如 Git 工作流、Laravel Mix 前端工作流等。
《L04 微信小程序从零到发布》
从小程序个人账户申请开始,带你一步步进行开发一个微信小程序,直到提交微信控制台上线发布。
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!