二叉树理论基础

满二叉树

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

完全二叉树

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第h层（h从1开始），则该层包含1~2^(h-1)个节点。
优先级队列其实是一个堆，堆就是一棵完全二叉树，同时保证父子节点的顺序关系。

二叉搜索树

前面的树，都没有数值的，而二叉搜索树是有数值的了，二叉搜索树是一个有序树。

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

平衡二叉搜索树

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
C++中map、set、multimap、multiset的底层实现都是平衡二叉搜索树，所以map、set的增删操作时间时间复杂度是logn，
unordered_map、unordered_set底层实现是哈希表。

递归的三要素

确定递归函数的参数和返回值；
确定终止条件；
确定单层递归的逻辑；

二叉树的存储方式

链式存储

用指针。

顺序存储

用数组。

二叉树的定义

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int data): val(data), left(NULL), right(NULL);
};

刷题笔记day14

二叉树递归遍历

文章讲解：代码随想录
是否自己做出来通过全部用例：是

遇到的困难/犯的错误

递归遍历代码比较简单，逻辑比较难理解。

自己写的代码

前序：

class Solution {
public:
    void dfs(TreeNode* root, vector<int>& vec) {
        if (root == NULL) {
            return;
        }
        vec.push_back(root->val);
        dfs(root->left, vec);
        dfs(root->right, vec);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        
        vector<int> vec;
        dfs(root, vec);
        return vec;
    }
};

前序：

class Solution {
public:
    void dfs(TreeNode* root, vector<int>& vec) {
        if (root == NULL) {
            return;
        }
        dfs(root->left, vec);
        vec.push_back(root->val);
        dfs(root->right, vec);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        
        vector<int> vec;
        dfs(root, vec);
        return vec;
    }
};

后序：

class Solution {
public:
    void dfs(TreeNode* root, vector<int>& vec) {
        if (root == NULL) {
            return;
        }
        dfs(root->left, vec);
        dfs(root->right, vec);
        vec.push_back(root->val);
    }
    vector<int> preorderTraversal(TreeNode* root) {
        
        vector<int> vec;
        dfs(root, vec);
        return vec;
    }
};

看了题解后的收获

写递归要按照三要素来写：

确定递归函数的参数和返回值。
确定终止条件
确定单层递归的逻辑

二叉树迭代遍历

文章讲解：代码随想录
是否自己做出来通过全部用例：是

遇到的困难/犯的错误

迭代遍历的时候，中序遍历访问节点（遍历节点）和处理节点（将元素放进结果集）的顺序是不一致的情况。因此难以形成风格统一的代码。不过可以采用标记法，将放入栈中的元素做标记。处理节点时，只有在遇到标记后才把下一个元素放入结果集。

自己写的代码

看了题解后写的风格统一的迭代法代码：
前序：

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> stk;
        vector<int> res;
        if (root != NULL) stk.push(root);
        while (!stk.empty()) {
            TreeNode* cur = stk.top();
            if (cur != NULL) {
                stk.pop();
                if (cur->right) stk.push(cur->right);
                if (cur->left) stk.push(cur->left);
                stk.push(cur);
                stk.push(NULL);
            }
            else {
                stk.pop();
                cur = stk.top();
                res.push_back(cur->val);
                stk.pop();
            }
        }
        return res;
    }
};

中序：

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*> stk;
        vector<int> res;
        if (root != NULL) stk.push(root);
        while (!stk.empty()) {
            TreeNode* cur = stk.top();
            if (cur != NULL) {
                stk.pop();
                if (cur->right) stk.push(cur->right);
                stk.push(cur);
                stk.push(NULL);
                if (cur->left) stk.push(cur->left);
            }
            else {
                stk.pop();
                cur = stk.top();
                res.push_back(cur->val);
                stk.pop();
            }
        }
        return res;
    }
};

后序：

class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        stack<TreeNode*> stk;
        vector<int> res;
        if (root != NULL) stk.push(root);
        while (!stk.empty()) {
            TreeNode* cur = stk.top();
            if (cur != NULL) {
                stk.pop();
                stk.push(cur);
                stk.push(NULL);
                if (cur->right) stk.push(cur->right);
                if (cur->left) stk.push(cur->left);
            }
            else {
                stk.pop();
                cur = stk.top();
                res.push_back(cur->val);
                stk.pop();
            }
        }
        return res;
    }
};

看了题解后的收获

掌握了统一风格的二叉树遍历的迭代法。