【LeeCode】二叉树理论

二叉树分类

没有数值	满⼆叉树	如果⼀棵⼆叉树只有度为0的结点和度为2的结点，并且度为0的结点在同⼀层 上，则这棵⼆叉树为满⼆叉树 ​满⼆叉树，也可以说深度为k，有2^k-1个节点的⼆叉树
没有数值	完全⼆叉树	在完全⼆叉树中，除了最底层节点可能没填满外，其余每层节点数 都达到最⼤值，并且最下⾯⼀层的节点都集中在该层最左边的若⼲位置。 若最底层为第 h 层，则该层包含 1~ 2^h -1 个节点
有数值	⼆叉搜索树 (有序树)	若它的左⼦树不空，则左⼦树上所有结点的值均⼩于它的根结点的值； 若它的右⼦树不空，则右⼦树上所有结点的值均⼤于它的根结点的值； 它的左、右⼦树也分别为⼆叉排序树
有数值	平衡⼆叉搜索树 也称: AVL	它是 ⼀棵空树或它的左右两个⼦树的⾼度差的绝对值不超过1，并且左右两个⼦树都是⼀棵平衡 ⼆叉树

二叉树存储

⼆叉树可以链式存储(即，指针)，也可以顺序存储(即，数组)

链式存储	是通过指针把分布在散落在各个地址的节点串联⼀起 ​⽤链式表⽰的⼆叉树，更有利于我们理解，所以⼀般我们都是⽤链式存储⼆叉树。
顺序存储	元素在内存是连续分布的 如果⽗节点的数组下表是i，那左节点: i * 2 + 1，右节点: i * 2 + 2

二叉树的遍历

⼆叉树主要有两种遍历⽅式：【深度】 + 【广度】

深度优先遍历 (往下走,然后往回走)	前序遍历（递归法，迭代法）    根左右 中序遍历（递归法，迭代法）     左根右 后序遍历（递归法，迭代法）     左右根 一般使用栈(先进后出·)
⼴度优先遍历 (一层一层遍历完再往下走)	层次遍历（迭代法） 一般使用队列实现(FIFO, 先进先出)

二叉树的定义

二叉树的链式定义

/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/

⼆叉树的递归遍历

递归三要素: 1. 确定参数和返回值  2. 确定终止条件 3. 确定递归逻辑

学习参考

​​https://programmercarl.com​​