二叉树 — 学习笔记(一)

学习笔记：

二叉树主要分为满二叉树和完全二叉树（无数值）

满二叉树：1、一棵树只有度为2的节点和度为0的节点。 2、度为0的节点在同一层上

完全二叉树：1、除最底层节点可能没填满外，其余每层节点数都达到最大值。

2、最下面一层的节点都集中在该层最左边的位置。

二叉搜索树：有序树。

若左子树不为空，则左子树上所有结点的值均小于它的根节点的值。

若右子树不为空，则右子树上所有结点的值均大于它的根节点的值。

它的左、右子树也分别为二叉排序树。

平衡二叉搜索树：又称为AVL树（Adelson-Velsk and Landis），红黑树是其特殊的一种。

1、空树或左右两个子树的高度差的绝对值不超过1。

2、左右两颗子树都是一颗平衡二叉树。

此外，map、set、mulimap,multiset的底层实现都是平衡二叉树，插入删除查找性能都是O(logN)

unordered_map、unordered_set，底层实现是哈希表。增删改查的代价可以说是O(1),最坏是O(n)

二叉树的存储方式：链式存储（指针）和顺序存储（数组）。

链式存储：通过指针把分布在各个地址的节点串联在一起。（通常用这种方法）

顺序存储：元素在内存是连续分布的。遍历时：父节点的数组下标是i，它的左孩子就是 i * 2 + 1，右孩子就是 i * 2 + 2。

二叉树的深度和高度：

深度：从根节点到该节点的最长简单路径边数。

高度：从该节点到叶子节点的最长简单路径边数。

二叉树的定义方式：

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

遍历方式：

二叉树的遍历方式：

深度优先遍历：想往深走，遇到叶节点再往回走。前中后指的是中间节点的位置。

前序遍历（递归法，迭代法）中左右计算二叉树的深度中序遍历（递归法，迭代法）左中右后序遍历（递归法，迭代法）左右中计算二叉树的高度广度优先遍历：从左到右一层一层的去遍历二叉树。

层次遍历（迭代法）

深度优先遍历的递归写法：

递归方法三要素：1、函数参数和返回值 2、终止条件 3、递归逻辑

    //确定需要的参数是二叉树的根节点和保存结果的数组
    void preTraversal(TreeNode* cur, vector& vec) {
        //确定结束条件：当前节点为零，则结束
        if (cur == NULL) return;
        //确定递归逻辑。
        vec.push_back(cur->val);      //中
        preTraversal(cur->left, vec); //前
        preTraversal(cur->right, vec);//后
    }
    vector preorderTraversal(TreeNode* root) {
        vectorres;
        preTraversal(root, res);
        return res;
    }

以遍历前序遍历为例，中后遍历就是递归函数时顺序发生变化。

注意：1、递归函数构造的三要素。 2、传参数组要传指针，和地址。

102. 二叉树的层序遍历 - 力扣（LeetCode） (leetcode-cn.com)

    vector> levelOrder(TreeNode* root) {
        queueque;
        vector>res;
        //先将根节点压入队列
        if (root != NULL) que.push(root);
        while (!que.empty()) {
            //把当前根节点取出来，再把它的左右节点压进去
            int size = que.size();
            vectorvec;
            for (int i = 0; i < size; i++) {
                TreeNode* curRoot = que.front();
                que.pop();
                vec.push_back(curRoot->val);
                if (curRoot->left) que.push(curRoot->left);
                if (curRoot->right) que.push(curRoot->right);
            }
            res.push_back(vec);
        }
        return res;
    }

错误：1、判断队列是否不为空，再压入节点。一定一定记得while()判断之后再for()循环。

2、size要提前定义，再进入for循环，因为que的长度是变化的。

101. 对称二叉树 - 力扣（LeetCode） (leetcode-cn.com)

bool compare(TreeNode* left, TreeNode* right) {
    //判断节点是否为空
    if(left == NULL && right != NULL) return false;
    else if(left != NULL && right == NULL) return false;
    else if(left == NULL && right == NULL) return true;
    //判断数值是否相等
    else if(left->val != right->val) return false;

    //此时情况是左右子树不为空且数值相等的情况
    //递归逻辑
    int resOut = compare(left->left, right->right);
    int resIn = compare(left->right, right->left);
    int res = resOut && resIn;
    return res;
    }
    bool isSymmetric(TreeNode* root) {
        if (root == NULL) return false;
        return compare(root->left, root->right);
    }

更改一下递归逻辑可以变成判断两个二叉树是否相同，在两棵二叉树是否相同的基础上在主函数力更改可以变成判断是否是子二叉树

bool isSubtree(TreeNode* root, TreeNode* subRoot) {
        //如果要检查的子树为空，那么不用查了，肯定对的
        if(subRoot == NULL) return true;
        //如果要检查的子树不空，但root是空的，那也不用查了，错的。
        if(root == NULL) return false;
        //要么是它本身，要么是它左子树，要么是它的右子树
        return compare(root, subRoot) ||
        isSubtree(root->left, subRoot) || 
        isSubtree(root->right, subRoot);

    }

110. 平衡二叉树 - 力扣（LeetCode） (leetcode-cn.com)

int compare(TreeNode* root) {
        //确定终止条件
        if (root == NULL) {
            return 0;
        }
        //递归逻辑
        int leftHeight = compare(root->left);
        if (leftHeight == -1) return -1;
        int rightHeight = compare(root->right);
        if (rightHeight == -1) return -1;
        return abs(leftHeight-rightHeight) > 1 ? -1 : 1 + max(leftHeight, rightHeight);        
    }
    bool isBalanced(TreeNode* root) {
        int res = compare(root);
        return res == -1 ? false : true;
    }

257. 二叉树的所有路径 - 力扣（LeetCode） (leetcode-cn.com)

void traversal(TreeNode* cur, vector& path, vector& res) {
        //插入当前节点
        path.push_back(cur->val);
        //循环终止条件
        if (cur->left == NULL && cur->right ==NULL) {
            string sPath;
            for (int i = 0; i < path.size() - 1; i++) {
                sPath += to_string(path[i]);
                sPath += "->";
            }
            sPath += to_string(path[path.size() - 1]);
            res.push_back(sPath);
            return;
        }
        //递归逻辑
        if (cur->left) {
            traversal (cur->left, path, res);
            path.pop_back();
        }
        if (cur->right) {
            traversal (cur->right, path, res);
            path.pop_back();
        }
        return;
    }
    vector binaryTreePaths(TreeNode* root) {
        vectorresult;
        vectorpath;
        if (root == NULL) return result;
        traversal(root, path, result);
        return result;
    }

这个好2难啊。

404. 左叶子之和 - 力扣（LeetCode） (leetcode-cn.com)

int sumOfLeftLeaves(TreeNode* root) {
        //终止条件
        if (root == NULL) return 0;
        int leftValue = sumOfLeftLeaves(root->left);
        int rightValue = sumOfLeftLeaves(root->right);

        int midValue = 0;
        if (root->left && !root->left->left && !root->left->right) {
            midValue = root->left->val; 
        }
        int sum = midValue + leftValue + rightValue;
        return sum; 
    }

这个整体递归逻辑都不太行。

112. 路径总和 - 力扣（LeetCode） (leetcode-cn.com)

 bool trasver(TreeNode* cur, int sum) {
        //终止条件
        //到达叶节
         if (cur->left == NULL && cur->right == NULL) {
             sum -= cur->val;
             //路径相等
             if (sum == 0 ) return true;
             //径值不相等
             return false; 
         } 
         if (cur->left) {
             sum -= cur->val;
             if (trasver(cur->left, sum)) return true;
             sum += cur->val;
         }
         if (cur->right) {
             sum -= cur->val;
             if (trasver(cur->right, sum)) return true;
             sum += cur->val;
         }
         return false;
    }
    bool hasPathSum(TreeNode* root, int targetSum) {
        if (root == NULL) return false;
        bool res = trasver(root,targetSum);
        return res;
    }

654. 最大二叉树 - 力扣（LeetCode） (leetcode-cn.com)

TreeNode* constructMaximumBinaryTree(vector& nums) {
        //定义一个节点
       TreeNode* node = new TreeNode(0);
       //终止条件，数组中只有一个值，就是叶节点了
       if (nums.size() == 1) {
           node->val = nums[0];
           return node;
       }
        //找到数组中最大值和对应的下标
        int maxValue = 0;
        int maxIndex = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > maxValue) {
                maxValue = nums[i];
                maxIndex = i;
            }
        }
        //设置节点的值
        node->val = maxValue;
        //最大值所在左区间(需要大于1)，构造左子树
        if (maxIndex > 0) {
            //定义左区间的数组
            vectorleftVec(nums.begin(), nums.begin() + maxIndex);
            node->left = constructMaximumBinaryTree(leftVec);
        }
        //最大值所在右区间(需要大于1)，构造右子树
        if (nums.size() - maxIndex - 1 > 0) {
            //定义左区间的数组
            vectorrightVec(nums.begin() + maxIndex + 1, nums.end());
            node->right = constructMaximumBinaryTree(rightVec);
        }
        return node;
    }

106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode） (leetcode-cn.com)

class Solution {
public:
    TreeNode* traversal(vector& inorder, vector& postorder) {
    // 第一步：如果数组大小为零的话，说明是空节点了。
    if (postorder.size() == 0) return NULL;
    //第二步：如果不为空，那么取后序数组最后一个元素作为当前的根节点。
    int rootValue = postorder[postorder.size() - 1];
    TreeNode* root = new TreeNode(rootValue);
    //如果当前根节点为叶子节点,即后序数组中只有这一个元素
    if (postorder.size() == 1) return root;
    //第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
    int inorderIndex;
    for (int i = 0; i < inorder.size(); i++) {
        if (inorder[i] == rootValue){
            inorderIndex = i;
            //找到就可以退出
            break;
        }
    }
    //第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
    vectorinorderLeft(inorder.begin(), inorder.begin() + inorderIndex);
    vectorinorderRight(inorder.begin() + inorderIndex + 1, inorder.end());

    //第五步：切割后序数组，切成后序左数组和后序右数组
    //最后一个点舍去，后序左数组和后续右数组的大小应与中序左数组和中序右数组相同
    postorder.resize(postorder.size() - 1);
    vectorpostorderLeft(postorder.begin(), postorder.begin() + inorderLeft.size());
    vectorpostorderRight(postorder.begin() + inorderLeft.size(), postorder.end());
    //第六步：递归处理左区间和右区间
    root->left = traversal(inorderLeft, postorderLeft);
    root->right = traversal(inorderRight, postorderRight);
    //忘记返回根节点了
    return root;
    }
    TreeNode* buildTree(vector& inorder, vector& postorder) {
        if (inorder.size() == 0 || postorder.size() == 0) return NULL;
        return traversal(inorder, postorder);
    }
};

这个好难，还没理解透。

知识点补充：

vector是STL的容器之一，数据结构是一段连续的线性内存空间。

它是使用三个迭代器（可以理解成指针）来表示的。

对于空的 vector 容器，由于没有任何元素的空间分配， _Myfirst、_Mylast 和 _Myend 均为 null。

参考网站：代码随想录 (programmercarl.com)

C++ vector（STL vector）底层实现机制（通俗易懂） (biancheng.net)

二叉树 — 学习笔记(一)

C/C++/C#相关栏目本月热门文章