这种二叉树只有度为0或度为2的结点,每一层看上去都是满满的,所以叫做满二叉树。
满二叉树是深度为k,有2^(k-1)个结点的二叉树,如下:
其实就是从上到下、从左到右填充的二叉树,不一定要满,但是一定要按这样的顺序填充结点,中间不能有空缺。
这是一种有序的且结点有数值的二叉树,有序就是,一个结点如果存在子结点,那么左边的子结点小于它,右边的子结点大于它,这种二叉树又叫做二叉排序树。
因为是Adelson Velsky和Landis发明的,所以又叫做AVL树,它具有这样的性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是平衡二叉树。
C++中的map、set等容器的底层实现都是平衡二叉树,所以要知道有这个东西。
二叉树主要有两大类遍历方式:深度优先遍历和广度优先遍历。
其中,深度优先遍历又分为:前序遍历、中序遍历和后序遍历;广度优先遍历就是层次遍历。
面试要求手写代码,所以得掌握二叉树的定义代码,关键时候做到可以手搓二叉树才行!
- struct TreeNode {
- int val; // 结点的值
- TreeNode* left; // 指向左子树
- TreeNode* right; // 指向右子树
- TreeNode(int x): val(x), left(NULL), right(NULL) {} //构造函数,初始化一个二叉树的时候,根结点赋值为x,其中左右子树都为空
- };
递归算法有三要素:
二叉树遍历的递归法讲究的就是一个格式,在外边再定义一个用于递归求解的函数reverser,参数是递归的二叉树当前根节点和用于保存遍历得到的答案序列的vector容器;
函数中的格式就是,先写递归终止条件,也就是遍历的结点为空时,直接return,退出这轮遍历;再写遍历的操作,对于前序遍历,就是先保存当前结点的值,放入容器中,再递归调用reverser函数,分别先后遍历左子树和右子树。中序遍历和后序遍历就是调整三个操作的位置即可。
- class Solution {
- public:
- void traverser(TreeNode* cur, vector<int> &vec) {
- if (cur == NULL) return;
- vec.push_back(cur->val);
- traverser(cur->left, vec);
- traverser(cur->right, vec);
- }
- vector<int> preorderTraversal(TreeNode* root) {
- vector<int> result;
- traverser(root, result);
- return result;
- }
- };
- class Solution {
- public:
- void reverser(TreeNode* cur, vector<int> &vec) {
- if (cur == NULL) return;
- reverser(cur->left, vec);
- vec.push_back(cur->val);
- reverser(cur->right, vec);
- }
- vector<int> inorderTraversal(TreeNode* root) {
- vector<int> result;
- reverser(root, result);
- return result;
- }
- };
- class Solution {
- public:
- void reverser(TreeNode* cur, vector<int> &vec) {
- if (cur == NULL) return;
- reverser(cur->left, vec);
- reverser(cur->right, vec);
- vec.push_back(cur->val);
- }
- vector<int> postorderTraversal(TreeNode* root) {
- vector<int> result;
- reverser(root, result);
- return result;
- }
- };
迭代遍历就是不用递归的遍历,是用栈来实现的,不断地将结点入栈出栈,直到栈为空时,整个二叉树就都遍历过了。
设置一个栈来作为遍历二叉树的工具,每次遍历到的结点都暂存在栈里,当我们遍历了这个结点后,就把这个结点出栈,然后将它的值放入result中。
对于前序遍历,需要先判断树是否为空,空的话就直接返回此时同样为空的result,不为空的话就将根结点入栈,然后开始用一个while循环遍历,终止条件是栈空了;
前序遍历是按照“根、左、右”的顺序遍历的,所以每次循环开始时,就把栈顶元素出栈,然后将这个结点的值放入result中,接着依次遍历右子树和左子树,为什么是这样的顺序呢?因为只有先把右边的入栈,出栈的时候才是左边先。
在依次遍历左右子树的时候,要先判断是否为空,没加判断的时候一直报错,我还以为是前面的出问题了,仔细对了一遍代码才知道是这里没判断:
- if (node->right) st.push(node->right);
- if (node->left) st.push(node->left);
- class Solution {
- public:
- vector<int> preorderTraversal(TreeNode* root) {
- stack
st; - vector<int> result;
- if (root == NULL) return result;
- st.push(root);
- while (!st.empty()) {
- TreeNode* node = st.top();
- st.pop();
- result.push_back(node->val);
- if (node->right) st.push(node->right);
- if (node->left) st.push(node->left);
- }
- return result;
- }
- };
按照“左、根、右”的思路来理解即可,预先准备的变量还是一个栈st和一个返回数组result,这次直接在外边定义一个指针cur来遍历二叉树;
遍历还是用的while循环,不过这里的终止条件是cur指向为空或者栈为空,两者其实等价,因为cur是遍历二叉树的,如果cur为空就说明二叉树都遍历完了,栈也同理;不过一般来说只是栈为空这项起作用,只要栈不为空,循环就一直进行下去;
循环里面就是两个分支,如果cur不指向空的话,就把cur指向的结点入栈,然后cur往左孩子移动;如果cur指向为空,也就是没有左孩子了,那说明遍历到最左下角了,“左”完了,那就让cur指向最后入栈的这个结点,也就是栈顶元素,将它出栈后,把它的值放进result里,这就把“根”遍历了,接下来就是“右”,把cur移向右孩子。
- class Solution {
- public:
- vector<int> inorderTraversal(TreeNode* root) {
- stack
st; - vector<int> result;
- TreeNode* cur = root;
- while (cur != NULL || !st.empty()) {
- if (cur != NULL) {
- st.push(cur);
- cur = cur->left;
- }
- else {
- cur = st.top();
- st.pop();
- result.push_back(cur->val);
- cur = cur->right;
- }
- }
- return result;
- }
- };
这里有一个很神奇的发现,如果我们按照 “根右左” 的顺序来遍历二叉树,其实和后序遍历得到的序列刚好相反!知道了这个有趣的事实,只需要在前序遍历的代码上稍作修改就可以得到后序遍历的代码了。
- class Solution {
- public:
- vector<int> postorderTraversal(TreeNode* root) {
- vector<int> result;
- stack
st; - if (root == NULL) return result;
- st.push(root);
- while (!st.empty()) {
- TreeNode* cur = st.top();
- st.pop();
- result.push_back(cur->val);
- if (cur->left) st.push(cur->left);
- if (cur->right) st.push(cur->right);
- }
- reverse(result.begin(), result.end());
- return result;
- }
- };
太难了,看不懂也没视频,二刷再学!