2023年6月22日发(作者：)

树常见题⽬总结1.树的前序遍历递归：class Solution {public: vector preorderTraversal(TreeNode* root) { vector ans; preorder(ans,root); return ans; } void preorder(vector &ans,TreeNode* root) { if(root == NULL) return; _back(root->val); preorder(ans,root->left); preorder(ans,root->right); }};⾮递归：class Solution {public: vector preorderTraversal(TreeNode* root){ vector res; stack tmp; if(root != NULL){ (root); } while(!()){ _back(() -> val); root = (); (); if(root -> right != NULL){ (root -> right); } if(root -> left != NULL){ (root -> left); } } return res; }};2.中序遍历递归：class Solution {public: vectorinorderTraversal(TreeNode* root){ vectorres; inorder(root,res); return res; } void inorder(TreeNode* root,vector& res){ if(root == NULL){ return; } inorder(root -> left,res); _back(root -> val); inorder(root -> right,res); }};⾮递归：class Solution {public: vector inorderTraversal(TreeNode* root) { vector res; stacktmp; while(root != NULL || !()){ if(root != NULL){ (root); root = root -> left; } else{ root = (); _back(root -> val); (); root = root -> right; } } return res; }};3.后序遍历递归：class Solution {public: vector postorderTraversal(TreeNode* root){ vectorres; postorder(res,root); return res; } void postorder(vector &res,TreeNode* root){ if(root == NULL){ return; } postorder(res,root -> left); postorder(res,root -> right); _back(root -> val); }};⾮递归：class Solution {public: vector postorderTraversal(TreeNode* root) { vector res; stack tmp1; stack tmp2; if(root != NULL){ (root); while(!()){ root = (); (()); (); if(root -> left != NULL) (root -> left); if(root -> right != NULL) (root -> right); } } while(!()){ _back(() -> val); (); } return res; }};4.重建⼆叉树题⽬描述：输⼊某的前序遍历和中序遍历的结果，请重建出该⼆叉树。假设输⼊的前序遍历和中序遍历的结果中都不含重复的数字。例如输⼊前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建⼆叉树并返回。实现代码：class Solution {public: TreeNode* reConstructBinaryTree(vector pre,vector vin) { if(() == 0){ //如果为空，返回NULL return NULL; } //依次是前序遍历左⼦树，前序遍历右⼦树，中序遍历左⼦树，中序遍历右⼦树 vector left_pre, right_pre, left_vin, right_vin; //中序遍历第⼀个节点⼀定为根节点 TreeNode* head = new TreeNode(pre[0]); //找到中序遍历的根节点 int root = 0; //遍历找到中序遍历根节点索引值 for(int i = 0; i < (); i++){ if(pre[0] == vin[i]){ root = i; break; } } //利⽤中序遍历的根节点，对⼆叉树节点进⾏归并 for(int i = 0; i < root; i++){ left__back(vin[i]); left__back(pre[i + 1]); //前序遍历第⼀个为根节点 }

for(int i = root + 1; i < (); i++){ right__back(vin[i]); right__back(pre[i]); }

//递归，再对其进⾏上述所有步骤，即再区分⼦树的左、右⼦⼦数，直到叶节点 head->left = reConstructBinaryTree(left_pre, left_vin); head->right = reConstructBinaryTree(right_pre, right_vin); return head; }};5.树的⼦结构题⽬描述：输⼊两颗⼆叉A，B，判断B是不是A的⼦结构。（PS：我们约定空树不是任意⼀个树的⼦结构）。实现代码：class Solution {public: bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) { bool result = false; if(pRoot1 != NULL && pRoot2 != NULL){ if(pRoot1->val == pRoot2->val){ result = DoesTree1HasTree2(pRoot1, pRoot2); } if(!result){ result = HasSubtree(pRoot1->left, pRoot2); } if(!result){ result = HasSubtree(pRoot1->right, pRoot2); } } return result; }private: bool DoesTree1HasTree2(TreeNode* pRoot1, TreeNode* pRoot2){ if(pRoot2 == NULL){ return true; } if(pRoot1 == NULL){ return false; } if(pRoot1->val != pRoot2->val){ return false; } return DoesTree1HasTree2(pRoot1->left, pRoot2->left) && DoesTree1HasTree2(pRoot1->right, pRoot2->right); }};6.⼆叉树的镜像题⽬描述：操作给定的⼆叉，将其变换为源⼆叉树的镜像。如下图所⽰：实现代码：class Solution {public: void Mirror(TreeNode *pRoot) { if((pRoot == NULL) || (pRoot->left == NULL && pRoot->right == NULL)){ return; }

//交换根节点的左右结点 TreeNode *pTemp = pRoot->left; pRoot->left = pRoot->right; pRoot->right = pTemp;

//递归左⼦树 if(pRoot->left){ Mirror(pRoot->left); } //递归右⼦树 if(pRoot->right){ Mirror(pRoot->right); } }};7.从上往下打印⼆叉树题⽬描述：从上往下打印出⼆叉的每个节点，同层节点从左⾄右打印。实现代码：class Solution {public: vector PrintFromTopToBottom(TreeNode* root) { TreeNode* fr; if(root == NULL){ return result; } (root); while(!()){ fr = (); _back(fr->val); if(fr->left != NULL){ (fr->left); } if(fr->right != NULL){ (fr->right); } (); } return result; }private: vector result; queue que;};8.⼆叉树中和为某⼀路径的值题⽬描述：输⼊⼀颗和⼀个整数，打印出中结点值的和为输⼊整数的所有路径。路径定义为从树的根结点开始往下⼀直到叶结点所经过的结点形成⼀条路径。实现代码：class Solution {public: vector > FindPath(TreeNode* root,int expectNumber){ if(root == NULL){ return result; }

_back(root->val); if((expectNumber - root->val ) == 0 && root->left == NULL && root->right == NULL){ _back(tmp); }

//遍历左⼦树 FindPath(root->left, expectNumber - root->val); //遍历右⼦树 FindPath(root->right, expectNumber - root->val);

_back(); return result; }private: vector > result; vector tmp;};9.⼆叉树的深度题⽬描述：输⼊⼀棵，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的⼀条路径，最长路径的长度为树的深度。实现代码：class Solution {public: int TreeDepth(TreeNode* pRoot) { if(pRoot == NULL){ return 0; } int left = TreeDepth(pRoot->left); int right = TreeDepth(pRoot->right); return (left > right) ? (left + 1) : (right + 1); }};10.判断是否为平⾏⼆叉树题⽬描述：的定义是：所谓的平衡之意，就是树中任意⼀个结点下左右两个⼦树的⾼度差不超过 1。实现代码：class Solution {public: bool IsBalanced_Solution(TreeNode* pRoot) { if(pRoot == NULL){ return true; } int left = TreeDepth(pRoot->left); int right = TreeDepth(pRoot->right); int diff = left - right; if(diff > 1 || diff < -1){ return false; } return IsBalanced_Solution(pRoot->right) && IsBalanced_Solution(pRoot->left); }private: int TreeDepth(TreeNode* pRoot) { if(pRoot == NULL){ return 0; } int left = TreeDepth(pRoot->left); int right = TreeDepth(pRoot->right); return (left > right) ? (left + 1) : (right + 1); }};11.⼆叉树的下⼀个节点题⽬描述：给定⼀个和其中的⼀个结点，请找出中序遍历顺序的下⼀个结点并且返回。注意，树中的结点不仅包含左右⼦结点，同时包含指向⽗结点的指针。实现代码：class Solution {public: TreeLinkNode* GetNext(TreeLinkNode* pNode) { if(pNode == NULL){ return NULL; } TreeLinkNode* pNext = NULL; // 当前结点有右⼦树，那么它的下⼀个结点就是它的右⼦树中最左⼦结点 if(pNode->right != NULL){ TreeLinkNode* pRight = pNode->right; while(pRight->left != NULL){ pRight = pRight-> left; } pNext = pRight; } // 当前结点⽆右⼦树，则需要找到⼀个是它⽗结点的左⼦树结点的结点 else if(pNode->next != NULL){ // 当前结点 TreeLinkNode* pCur = pNode; // ⽗节点 TreeLinkNode* pPar = pNode->next; while(pPar != NULL && pCur == pPar->right){ pCur = pPar; pPar = pCur->next; } pNext = pPar; } return pNext; }};12.对称⼆叉树题⽬描述：请实现⼀个函数，⽤来判断⼀颗是不是对称的。注意，如果⼀个⼆叉树同此⼆叉树的镜像是同样的，定义其为对称的。实现代码：class Solution {public: bool isSymmetrical(TreeNode* pRoot) { if(pRoot == NULL){ return true; } return isSymmetriacalCor(pRoot, pRoot); }private: bool isSymmetriacalCor(TreeNode* pRoot1, TreeNode* pRoot2){ if(pRoot1 == NULL && pRoot2 == NULL){ return true; } if(pRoot1 == NULL || pRoot2 == NULL){ return false; } if(pRoot1->val != pRoot2->val){ return false; } return isSymmetriacalCor(pRoot1->left, pRoot2->right) && isSymmetriacalCor(pRoot1->right, pRoot2->left); }};13.之字形打印⼆叉树题⽬描述：请实现⼀个函数按照之字形打印，即第⼀⾏按照从左到右的顺序打印，第⼆层按照从右⾄左的顺序打印，第三⾏按照从左到右的顺序打印，其他⾏以此类推。实现代码：class Solution {public: vector > Print(TreeNode* pRoot) { vector > result; if(pRoot == NULL){ return result; } stack s[2]; s[0].push(pRoot); while(!s[0].empty() || !s[1].empty()){ vector v[2]; // 偶数⾏ while(!s[0].empty()){ v[0].push_back(s[0].top()->val); if(s[0].top()->left != NULL){ s[1].push(s[0].top()->left); } if(s[0].top()->right != NULL){ s[1].push(s[0].top()->right); } s[0].pop(); } if(!v[0].empty()){ _back(v[0]); } // 奇数⾏ while(!s[1].empty()){ v[1].push_back(s[1].top()->val); if(s[1].top()->right != NULL){ s[0].push(s[1].top()->right); } if(s[1].top()->left != NULL){ s[0].push(s[1].top()->left); } s[1].pop(); } if(!v[1].empty()){ _back(v[1]); } } return result; }};14.把⼆叉树打印成多⾏题⽬描述：从上到下按层打印⼆叉树，同⼀层结点从左⾄右输出。每⼀层输出⼀⾏。实现代码：class Solution {public: vector > Print(TreeNode* pRoot) { vector > result; if(pRoot == NULL){ return result; } queue nodes[2]; nodes[0].push(pRoot); while(!nodes[0].empty() || !nodes[1].empty()){ vector v[2]; while(!nodes[0].empty()){ v[0].push_back(nodes[0].front()->val); if(nodes[0].front()->left != NULL){ nodes[1].push(nodes[0].front()->left); } if(nodes[0].front()->right != NULL){ nodes[1].push(nodes[0].front()->right); } nodes[0].pop(); } if(!v[0].empty()){ _back(v[0]); } while(!nodes[1].empty()){ v[1].push_back(nodes[1].front()->val); if(nodes[1].front()->left != NULL){ nodes[0].push(nodes[1].front()->left); } if(nodes[1].front()->right != NULL){ nodes[0].push(nodes[1].front()->right); } nodes[1].pop(); } if(!v[1].empty()){ _back(v[1]); } } return result; }};15.序列化⼆叉树题⽬描述：请实现两个函数，分别⽤来序列化和反序列化。实现代码：class Solution {public: char* Serialize(TreeNode *root) {

if(!root){ return NULL; } string str; SerializeCore(root, str); // 把str流中转换为字符串返回 int length = (); char* res = new char[length+1]; // 把str流中转换为字符串返回 for(int i = 0; i < length; i++){ res[i] = str[i]; } res[length] = '0'; return res; } TreeNode* Deserialize(char *str) { if(!str){ return NULL; } TreeNode* res = DeserializeCore(&str); return res; } void SerializeCore(TreeNode* root, string& str){ // 如果指针为空，表⽰左⼦节点或右⼦节点为空，则在序列中⽤#表⽰ if(!root){ str += '#'; return; } string tmp = to_string(root->val); str += tmp; // 加逗号，⽤于区分每个结点 str += ','; SerializeCore(root->left, str); SerializeCore(root->right, str); } // 递归时改变了str值使其指向后⾯的序列，因此要声明为char** TreeNode* DeserializeCore(char** str){ // 到达叶节点时，调⽤两次，都返回null，所以构建完毕，返回⽗节点的构建 if(**str == '#'){ (*str)++; return NULL; } // 因为整数是⽤字符串表⽰，⼀个字符表⽰⼀位，先进⾏转换 int num = 0; while(**str != ',' && **str != '0'){ num = num * 10 + ((**str) - '0'); (*str)++; } TreeNode* root = new TreeNode(num); if(**str == '0'){ return root; } else{ (*str)++; } root->left = DeserializeCore(str); root->right = DeserializeCore(str); return root; }};16.⼆叉树的最⼩树深题⽬描述：

给定⼀个⼆叉树，找出其最⼩深度。最⼩深度是从根节点到最近叶⼦节点的最短路径上的节点数量。说明: 叶⼦节点是指没有⼦节点的节点。⽰例:给定⼆叉树 [3,9,20,null,null,15,7], 3 / 9 20 / 15 7返回它的最⼩深度 2.实现代码：class Solution {public: int digui(TreeNode* root){ if(root->left == NULL && root->right == NULL){ return 1; } else if(root->left == NULL && root->right != NULL){ return 1 + digui(root->right); } else if(root->left != NULL && root->right == NULL){ return 1 + digui(root->left); } else{ return 1 + min(digui(root->left),digui(root->right)); } } int minDepth(TreeNode* root) { if(root == NULL){ return 0; } else{ return digui(root); } }};17.⼆叉树的最⼤树深题⽬描述：给定⼀个⼆叉树，找出其最⼤深度。⼆叉树的深度为根节点到最远叶⼦节点的最长路径上的节点数。说明: 叶⼦节点是指没有⼦节点的节点。⽰例：给定⼆叉树 [3,9,20,null,null,15,7]， 3 / 9 20 / 15 7返回它的最⼤深度 3 。实现代码：class Solution {public: int digui(TreeNode* root){ if(root == NULL){ return 0; } else{ return 1 + max(digui(root->left),digui(root->right)); } } int maxDepth(TreeNode* root) { int i = 0; if(root == NULL) { return 0; } else {

i = digui(root); } return i; }};18.最长同值路径题⽬描述：给定⼀个⼆叉树，找到最长的路径，这个路径中的每个节点具有相同值。 这条路径可以经过也可以不经过根节点。注意：两个节点之间的路径长度由它们之间的边数表⽰。⽰例 1:输⼊: 5 / 4 5 / 1 1 5输出:2⽰例 2:输⼊: 1 / 4 5 / 4 4 5输出:2注意: 给定的⼆叉树不超过10000个结点。 树的⾼度不超过1000。实现代码：class Solution {public: int current_max=0; int longestUnivaluePath(TreeNode* root) { dfs(root); return current_max; }

int dfs(TreeNode* root){ if(root==NULL){ return 0; } int left=dfs(root->left); int right=dfs(root->right); if(root->left!=NULL&&root->val==root->left->val){ left+=1; }else{ left=0; } if(root->right!=NULL&&root->val==root->right->val){ right+=1; }else{ right=0;

} current_max=max(current_max,left+right); return max(left,right); }};19.⼆叉搜索树节点最⼩距离题⽬描述：给定⼀个⼆叉搜索树的根结点 root, 返回树中任意两节点的差的最⼩值。⽰例：输⼊: root = [4,2,6,1,3,null,null]输出: 1解释:注意，root是树结点对象(TreeNode object)，⽽不是数组。给定的树 [4,2,6,1,3,null,null] 可表⽰为下图: 4 / 2 6 /

1 3

最⼩的差值是 1, 它是节点1和节点2的差值, 也是节点3和节点2的差值。注意： ⼆叉树的⼤⼩范围在 2 到 100。 ⼆叉树总是有效的，每个节点的值都是整数，且不重复。实现代码：class Solution {public: void pre(vector &res,TreeNode *root){ if(root != NULL){ pre(res,root->left); _back(root->val); pre(res,root->right); } } int minDiffInBST(TreeNode* root) { vector res; pre(res,root); vector r; int min = 0; for(int i = 0;i < () - 1;i++){ _back(res[i+1]-res[i]); } sort((),()); return r[0]; }};20.⼆叉搜索树的范围和题⽬描述：给定⼆叉搜索树的根结点 root，返回 L 和 R（含）之间的所有结点的值的和。⼆叉搜索树保证具有唯⼀的值。 ⽰例 1：输⼊：root = [10,5,15,3,7,null,18], L = 7, R = 15输出：32⽰例 2：输⼊：root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10输出：23

提⽰： 树中的结点数量最多为 10000 个。 最终的答案保证⼩于 2^31。实现代码：class Solution {public: void pre(vector &res,TreeNode * root){ if(root != NULL){ pre(res,root->left); _back(root->val); pre(res,root->right); } } int rangeSumBST(TreeNode* root, int L, int R) { int value = 0; vectorres; pre(res,root); for(int i = 0;i < ();i++){ if(res[i] >= L&&res[i] <= R) { value = value + res[i]; } } return value; }};21.⼆叉搜索树的后序遍历序列题⽬描述：输⼊⼀个整数数组，判断该数组是不是某⼆叉搜索树的后序遍历的结果。如果是则输出Yes，否则输出No。假设输⼊的数组的任意两个数字都互不相同。实现代码：class Solution {public: bool VerifySquenceOfBST(vector sequence) { return bst(sequence, 0, () - 1); }private: bool bst(vector seq, int begin, int end){ if(() || begin > end){ return false; }

//根结点 int root = seq[end];

//在⼆叉搜索树中左⼦树的结点⼩于根结点 int i = begin; for(; i < end; ++i){ if(seq[i] > root){ break; } }

//在⼆叉搜索书中右⼦树的结点⼤于根结点 for(int j = i; j < end; ++j){ if(seq[j] < root){ return false; } }

//判断左⼦树是不是⼆叉搜索树 bool left = true; if(i > begin){ left = bst(seq, begin, i - 1); }

//判断右⼦树是不是⼆叉搜索树 bool right = true; if(i < end - 1){ right = bst(seq, i , end - 1); }

return left && right; }};22.⼆叉搜索树第k个节点题⽬描述：给定⼀颗⼆叉搜索树，请找出其中的第k⼤的结点。例如，在下图中，按结点数值⼤⼩顺序第三个结点的值为4。这棵树是⼆叉搜索树，⾸先想到的是⼆叉搜索树的⼀个特点：左⼦结点的值 < 根结点的值 < 右⼦结点的值。实现代码：class Solution {public: TreeNode* KthNode(TreeNode* pRoot, int k) { if(pRoot == NULL || k == 0){ return NULL; } return KthNodeCore(pRoot, k); }private: TreeNode* KthNodeCore(TreeNode* pRoot, int &k){ TreeNode* target = NULL; // 先遍历左结点 if(pRoot->left != NULL){ target = KthNodeCore(pRoot->left, k); } // 如果没有找到target，则继续减⼩k，如果k等于1，说明到了第k⼤的数 if(target == NULL){ if(k == 1){ target = pRoot; } k--; } // 如果没有找到target，继续找右结点 if(pRoot->right != NULL && target == NULL){ target = KthNodeCore(pRoot->right, k); } return target; }};