跳到主要内容

简介

哥们来复习了，二叉树忘得还是有点厉害的

二叉树的种类​

  1. 满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树
  2. 完全二叉树：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层（h从1开始），则该层包含 1~ 2^(h-1) 个节点
  3. 二叉搜索树：二叉搜索树是一个有序树。
    • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
    • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
    • 它的左、右子树也分别为二叉排序树
  4. 平衡二叉搜索树：是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

前序：

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

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

    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> vector1;
        traversal(root, vector1);
        return vector1;
    }
};

迭代法前序遍历

    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode *> stack1;
        vector<int> vector1;
        if(root== NULL)return vector1;
        stack1.push(root);
        while(!stack1.empty()) {
            TreeNode *temp = stack1.top();//中间先出栈
            stack1.pop();//弹出
            vector1.push_back(temp->val);
            if(temp->right!= NULL)stack1.push(temp->right);//先塞右边的，出来的时候先出左边
            if(temp->left!= NULL)stack1.push(temp->left);
        }
        return vector1;
    }

中序遍历​

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> ans;
        stack<TreeNode *> stk;
        TreeNode *temp = root;
//        if(root== nullptr)return ans;
//        stk.push(temp);
        while (temp != NULL || !stk.empty()) {
            if(temp!= nullptr) {
                stk.push(temp);
                temp = temp->left;
            } else {
                temp = stk.top();
                stk.pop();
                ans.push_back(temp->val);
//                stk.push(temp->right); 这个错了
                temp=temp->right;
            }

        }
        return ans;
    }