C++学习笔记5——二叉树

基本概念二叉树是每个节点最多有两个子节点的树结构分别称为左子节点和右子节点。节点包含三个信息——值value、左子节点指针和右子结点指针。结构函数struct TreeNode { int val; // 节点值 TreeNode* left; // 左子节点指针 TreeNode* right; // 右子节点指针 // 构造函数 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode* l, TreeNode* r) : val(x), left(l), right(r) {} };术语说明根节点树的顶部节点没有父节点叶子节点没有子节点的节点父节点有子节点的节点子节点节点的直接下属兄弟节点同一个父节点的节点深度从根到节点的距离高度从节点到最远叶子的距离子树节点及其所有后代基本类型1.满二叉树Full Binary Tree每个节点要么是叶子要么有两个子节点。2.完全二叉树Complete Binary Tree除了最后一层其他层都满最后一层节点靠左排列。3.完美二叉树Perfect Binary Tree所有叶子节点都在同一层每个非叶子节点都有两个子节点。4.平衡二叉树Balanced Binary Tree左右子树高度差不超过1。5.二叉搜索树BST左子树所有节点 根节点 右子树所有节点。遍历方式二叉树有两种遍历方式1.深度优先遍历DFS沿着一条路径一直走到尽头然后回溯再走另一条路径。方法A递归法遍历前中后class Solution { public: void traversal(TreeNode* cur, vectorint vec) { if (cur NULL) return; //前序遍历 vec.push_back(cur-val); // 中 traversal(cur-left, vec); // 左 traversal(cur-right, vec); // 右 //中序遍历 //traversal(cur-left, vec); // 左 //vec.push_back(cur-val); // 中 //traversal(cur-right, vec); // 右 //后序遍历 //traversal(cur-left, vec); // 左 //traversal(cur-right, vec); // 右 //vec.push_back(cur-val); // 中 } vectorint preorderTraversal(TreeNode* root) { vectorint result; traversal(root, result); return result; } };例如前序遍历访问根结点再访问左子树、再访问右子树ABDECFG中序遍历DBEAFCG后序遍历DEBFGCA方法BBoolean标记-迭代法遍历前中后class Solution { public: vectorint inorderTraversal(TreeNode* root) { vectorint result; stackpairTreeNode*, bool st; if (root ! nullptr) st.push(make_pair(root, false)); // 多加一个参数false 为默认值含义见下文注释 while (!st.empty()) { auto node st.top().first; auto visited st.top().second; //多加一个 visited 参数使“迭代统一写法”成为一件简单的事 st.pop(); if (visited) { // visited 为 True表示该节点和两个儿子位次之前已经安排过了现在可以收割节点了 result.push_back(node-val); continue; } // visited 当前为 false, 表示初次访问本节点此次访问的目的是“把自己和两个儿子在栈中安排好位次”。 // 中序遍历 if (node-right) st.push(make_pair(node-right, false)); //右儿子最先入栈最后出栈 st.push(make_pair(node, true)); // 把自己加回到栈中位置居中同时设置 visited 为 true表示下次再访问本节点时允许收割。 if (node-left) st.push(make_pair(node-left, false)); // 左儿子最后入栈最先出栈 // 前序遍历 //if (node-right) st.push(make_pair(node-right, false)); //右 //if (node-left) st.push(make_pair(node-left, false)); // 左 //st.push(make_pair(node, true)); // 中 // 后序遍历 //st.push(make_pair(node, true)); // 中 //if (node-right) st.push(make_pair(node-right, false)); //右 //if (node-left) st.push(make_pair(node-left, false)); // 左 } return result; } };2.层序遍历BFS按层次一层一层地遍历先访问完当前层的所有节点再访问下一层。class Solution { public: vectorvectorint levelOrder(TreeNode* root) { queueTreeNode* que; if (root ! NULL) que.push(root); vectorvectorint result; while (!que.empty()) { int size que.size(); vectorint vec; // 这里一定要使用固定大小size不要使用que.size()因为que.size是不断变化的 for (int i 0; i size; i) { TreeNode* node que.front(); que.pop(); vec.push_back(node-val); if (node-left) que.push(node-left); if (node-right) que.push(node-right); } result.push_back(vec); } return result; } };3. 两者差异方面DFSBFS核心思想深入到底再回溯逐层推进数据结构栈队列空间树高树宽适用路径、存在性最短路径、分层实现递归简单迭代简单4. 常见问题及思路· 求二叉树深度层序遍历每层计数加一class Solution { public: int maxDepth(TreeNode* root) { queueTreeNode* que; vectorvectorint res; if(rootNULL) return 0; que.push(root); int x; while(!que.empty()){ x; //计算层数深度 int size que.size(); for(int i0;isize;i){ TreeNode* cur que.front(); que.pop(); if(cur-left) que.push(cur-left); if(cur-right) que.push(cur-right); } } return x; } };·翻转二叉树层序遍历每层左右子树互换class Solution { public: TreeNode* invertTree(TreeNode* root) { queueTreeNode* que; if(rootNULL) return NULL; que.push(root); while(!que.empty()){ int size que.size(); for(int i 0;isize;i){ TreeNode* cur que.front(); que.pop(); TreeNode* temp cur-left; //翻转 cur-left cur-right; cur-right temp; if(cur-left) que.push(cur-left); if(cur-right) que.push(cur-right); } } return root; } };· 求二叉树左/右视图层序遍历按左/右顺序依次输出// 二叉树右视图 class Solution { public: vectorint rightSideView(TreeNode* root) { queueTreeNode* que; vectorint res; if(rootNULL) return res; que.push(root); while(!que.empty()){ int size que.size(); for(int i0;isize;i){ TreeNode* cur que.front(); que.pop(); if(cur-right) que.push(cur-right); //先右后左入列 if(cur-left) que.push(cur-left); if(i0) res.push_back(cur-val); //输出每层最右侧节点值 } } return res; } };· 判断对称二叉树深度遍历每次递归设置双指针左右同时便历class Solution { public: bool x 1; void check(TreeNode* p,TreeNode* q){ if(pNULLqNULL) return; if(pNULL||qNULL||p-val!q-val){ x 0; //不对称条件两镜像节点存在性不同或值不同 return; } check(p-left,q-right); check(p-right,q-left); } bool isSymmetric(TreeNode* root) { if(rootNULL) return true; check(root-left,root-right); return x; } };· 求二叉树直径深度遍历每次递归计算当前节点的左右最大深度和、返回当前节点的最大深度class Solution { public: int res 1; int depth(TreeNode* node){ if(nodeNULL) return 0; int L depth(node-left); int R depth(node-right); int depth_cur max(L,R)1; //1为了保证迭代有效其他参数也等效1 res max(LR1,res); //计算当前节点的左右最大深度和 return depth_cur; //返回当前节点的最大深度 } int diameterOfBinaryTree(TreeNode* root) { depth(root); return res-1; } };· 将升序数组转换为二叉搜索树中序遍历二分法每次递归制造新的根节点、嵌套递归左右子树class Solution { public: TreeNode* helper(vectorint nums,int left,int right){ //二分法双指针在二叉树的应用 if(leftright) return NULL; int mid (leftright)/2; //生成当前节点root、root-value、root-left、root-right TreeNode* root new TreeNode(nums[mid]); root-left helper(nums,left,mid-1); //递归生成左子树(mid左半边) root-right helper(nums,mid1,right); //递归生成右子树(mid右半边) return root; } TreeNode* sortedArrayToBST(vectorint nums) { return helper(nums,0,nums.size()-1); } };· 验证二叉搜索树左右分区间递归class Solution { public: bool helper(TreeNode* node,long long lower,long long upper){ //函数功能计算一个子树是否满足搜索树条件返回true/false //终止条件当前节点不存在时默认满足搜索树条件返回true当前节点违背条件返回false if(nodeNULL) return true; if(node-vallower||node-valupper) return false; //不再继续搜索 //递归逻辑 //1.当节点的左右子树均满足搜索树条件时才等价于节点形成的子树满足条件 //2.搜索树条件左子树节点值∈(lower,node-val)右子树节点值∈(node-val,upper) return helper(node-left,lower,node-val)helper(node-right,node-val,upper); } bool isValidBST(TreeNode* root) { return helper(root,LONG_MIN,LONG_MAX); //初始化为-infinf } };· 求二叉搜索树中第k小的元素中序遍历二叉搜索树升序排列数组class Solution { public: void inorder(TreeNode* node, vectorint res){ if(nodeNULL) return; inorder(node-left,res); res.push_back(node-val); inorder(node-right,res); } int kthSmallest(TreeNode* root, int k) { vectorint res; //二叉搜索树中序遍历升序排列数组 inorder(root,res); return res[k-1]; } };-----------------------------------------------------关于递归递归是函数调用自身从而将问题分解为更小的、相同类型的子问题来解决原问题。递归的要点分为三部分函数功能、终止条件和递归逻辑1函数功能首先明确函数的功能、参数和返回值问题必须满足以下条件原问题可以分解为子问题子问题和原问题的求解方法是一致的即都是调用自身的同一个函数。2终止条件基本条件递归函数中的终止条件指明了递归调用何时应该停止即不能无限循环地调用本身。在递归函数的执行过程中当满足终止条件时递归调用将不再继续函数开始返回结果。例如计算阶乘的递归函数中的终止条件是当输入参数为 0 或 1 时直接返回 1。3递归逻辑递归逻辑的核心是需要找到原函数的一个等价关系式 从而确定每一层递归需要处理的信息。例如计算阶乘当n1时f(n) 的等价关系式为 n * f(n-1)int fac(int n) { //参数和返回值 // 终止条件n 0 或 n 1 if (n 0 || n 1) { return 1; } // 递归逻辑n 1时f(n)n * f(n-1) else { return n * fac(n - 1); } }---------------------------------------------------------------------------------------------------------------------------------