刷leetcodehot100返航版--二叉树

二叉树理论基础

二叉树的种类

满二叉树和完全二叉树，二叉树搜索树

满二叉树

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

节点个数2^n-1【n为树的深度】

完全二叉树

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

满二叉树一定是完全二叉树

二叉搜索树

二叉搜索树是有数值的了，二叉搜索树是一个有序树。

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

平衡二叉搜索树【AVL（Adelson-Velsky and Landis）树】

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

C++中map、set、multimap，multiset的底层实现都是平衡二叉搜索树，所以map、set的增删操作时间时间复杂度是logn【key有序】

而unordered_map、unordered_set底层实现是哈希表。

二叉树的存储方式

二叉树可以链式存储，也可以顺序存储。

那么链式存储方式就用指针， 顺序存储的方式就是用数组。

链式存储【构造二叉树：函数里面传参头指针】

数组【实际用的少】

遍历方式

DFS

中序前序后序【递归，栈；非递归，迭代】

左右中序指的是中的遍历顺序

BFS

层序遍历【迭代，队列，先进先出】

二叉树定义

struct TreeNode{

        int val;

        TreeNode* left;

        TreeNode* right;

        TreeNode(int x):val(x),left(NULL),right(NULL){}//构造函数

};

构造函数也可以不写，但是new一个新的节点的时候就比较麻烦。

例如有构造函数，定义初始值为9的节点：

TreeNode* a = new TreeNode(9);

而没有构造函数还得自己定义：

TreeNode* a = new TreeNode();
a->val = 9;
a->left = NULL;
a->right = NULL;

 二叉树遍历

递归三要素：

1.函数返回值和参数【函数头定义】2.确定结束条件【if（check）return】3.单层递归逻辑

不太懂这个结构体/二叉树怎么读进去的

1.中序遍历

94. 二叉树的中序遍历 - 力扣（LeetCode）

p.s.函数名字不要起太平常的，比如try什么的，可能和系统性的函数重名，出问题

p.s.对于返回值是void的递归函数，参数里的&是重点

感觉挺神奇的，只有root的val，也就是中可以放进数组

问题：这个输入是怎么读进去的

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {//没看懂//返回一个vector,必然不可以遍历vector<int> res;try1(root,res);return res;}void try1(TreeNode* root,vector<int>&res){if(root == nullptr){return;}//左中右try1(root->left,res);res.push_back(root->val);try1(root->right,res);}
};

2.之后迭代遍历【代码随想录】