算法笔记_面试题_16. 二叉树相关

朴灿烈づ我的快乐病毒、 2022-09-17 01:53 181阅读 0赞

**目录**

1. 基本概念

1.1 常考二叉树种类

1.2 二叉树的存储

1.3 遍历方式(贯穿整个leecode常考题目)

1.4 二叉树的定义

2. 相关题目

--------------------

# 1. 基本概念 #

参考: [代码随想录 carl][carl]

## **1.1 常考二叉树种类** ##

**面试中常考的关于二叉树的种类有以下4种:**

**满二叉树:** 每个节点的孩子节点要么是0个, 要么是2个. 也可以说深度为k，有2^k-1个节点的⼆叉树。

**完全二叉树:** 满二叉树, 若要是缺少节点,只能是**从右往左缺**.

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oOK6bi_5LiA5Y2a_size_20_color_FFFFFF_t_70_g_se_x_16][]

**二叉搜索树:** 所有的节点的左子节点到**大于**右子节点的值.

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oOK6bi_5LiA5Y2a_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

**平衡二叉搜索树:** 二叉搜索树中, 所有节点的左子树的**深度** \- 右子数的深度 <= 1.

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oOK6bi_5LiA5Y2a_size_20_color_FFFFFF_t_70_g_se_x_16 2][]

## **1.2 二叉树的存储** ##

链式存储, 左右指针(常用方式)

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oOK6bi_5LiA5Y2a_size_20_color_FFFFFF_t_70_g_se_x_16 3][]

线性存储, (左子节点:2i+1, 右子节点 2i+2) (不常用)

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oOK6bi_5LiA5Y2a_size_20_color_FFFFFF_t_70_g_se_x_16 4][]

## **1.3 遍历方式(贯穿整个leecode常考题目)** ##

深度优先遍历

前序遍历（递归法，迭代法）

中序遍历（递归法，迭代法）

后序遍历（递归法，迭代法）

⼴度优先遍历

层次遍历（迭代法）

## 1.4 二叉树的定义 ##

面试官可以考下,来,自己定义一个二叉树,做些xx操作.

struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode (int x) : val(x), left(null), right(null){}
    };

# 2. 相关题目 #

[carl]: https://www.bilibili.com/video/BV1Hy4y1t7ij?spm_id_from=333.999.0.0
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oOK6bi_5LiA5Y2a_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/d6d19826bfff4b58a525aa0004a932b1.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oOK6bi_5LiA5Y2a_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/b31a6ddd3cf64aa19499b7111e5f44e1.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oOK6bi_5LiA5Y2a_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/ee304fe86ba342cfb37bfb980afa83b9.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oOK6bi_5LiA5Y2a_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/cb1643a74fc647a093a01818b6f6f0f7.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5oOK6bi_5LiA5Y2a_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/9dee24a8f90d48c985377407ad538ba5.png