【剑指offer】树

📁 JZ55 二叉树的深度

        找左右子树深度的最大值，加上根这一层就是整棵二叉树的深度。

class Solution {
public:int TreeDepth(TreeNode* pRoot) {if(pRoot == nullptr)return 0;return max(TreeDepth(pRoot->left) , TreeDepth(pRoot->right)) + 1;}
};

📁 JZ27 二叉树的镜像

        一次简单的后续遍历即可，将根节点的左右指针互换，左指针指向右子树，右指针指向左子树即可，互换之前确保左右子树已经互换完成。

class Solution {
public:TreeNode* Mirror(TreeNode* pRoot) {// write code hereif(pRoot == nullptr)return nullptr;TreeNode* left = Mirror(pRoot->left);TreeNode* right = Mirror(pRoot->right);pRoot->right = left;pRoot->left = right;return pRoot;}
};

📁 JZ32 从上往下打印二叉树

        进行层序遍历，将遍历结果保存在数组中即可。

class Solution {
public:vector<int> PrintFromTopToBottom(TreeNode* root) {if(root == nullptr) {return vector<int>();}vector<int> ret;queue<TreeNode*> q;q.push(root);while(!q.empty()) {int sz = q.size();while(sz--){TreeNode* node = q.front();q.pop();ret.push_back(node->val);if(node->left)q.push(node->left);if(node->right)q.push(node->right);}}return ret;}
};

📁 JZ54 二叉搜索树的第k个节点

        最简单的方法就是将搜索二叉树的结果保存起来，通过中序遍历的方式，返回k-1下标的元素，注意处理好边界情况。

        第二种方法就是中序遍历，通过一个变量记录遍历到第几个元素，返回第k个元素即可。就是在第一个的基础上优化了数组而已。

class Solution {
public:int count = 0;int ans = -1;int KthNode(TreeNode* root, int k) {if(root == nullptr)return -1;KthNode(root->left,k);++count;if(count == k)ans = root->val;KthNode(root->right,k);return ans;}
};

📁 JZ77 按之字形顺序打印二叉树

        层序遍历，将节点的值放入数组中，处理奇偶层即可。

#include <asm-generic/errno.h>
#include <vector>
#include <queue>
class Solution {
public:vector<vector<int> > Print(TreeNode* pRoot) {if(pRoot == nullptr)return vector<vector<int>>();vector<vector<int>> ret;queue<TreeNode*> q;int index = 0;  //偶数从左往右 奇数从右往左q.push(pRoot);while(!q.empty()){int sz = q.size();vector<int> tmp;if(index % 2 == 0){for(int i = 0 ; i < sz ; ++i){   TreeNode* node = q.front();q.pop();tmp.push_back(node->val);if(node->left){q.push(node->left);}if(node->right){q.push(node->right);}}}else{for(int i = sz - 1 ; i >= 0 ; --i){   TreeNode* node = q.front();q.pop();tmp.push_back(node->val);if(node->left){q.push(node->left);}if(node->right){q.push(node->right);}}reverse(tmp.begin(), tmp.end());}ret.push_back(tmp);++index;}return ret;}
};

📁 JZ7 重建二叉树

        通过前序遍历，找到当前子树的根节点，通过中序遍历找到根节点的左右子树中序遍历的序列。

        该函数返回的是当前子树的根节点，因此可以使用递归特性。每次遍历创建子树的根节点，递归处理左右子树，向上返回左右子树的根节点，root修改指向即可。

class Solution {public:TreeNode* reConstructBinaryTree(vector<int>& pre, vector<int>& vin) {if (pre.size() == 0)return nullptr;int val = pre[0];TreeNode* root = new TreeNode(val);if (root == nullptr || pre.size() == 1)return root;//在中序遍历中 查找当前子树的根节点的下标int splitIndex = 0;for (; splitIndex < vin.size(); splitIndex++) {if (vin[splitIndex] == root->val)break;}// 左子树的前序遍历vector<int> leftPre(pre.begin() + 1, pre.begin() + splitIndex + 1);vector<int> rightPre(pre.begin() + splitIndex + 1, pre.end());// 左右子树的中序遍历vector<int> leftVin(vin.begin(), vin.begin() + splitIndex);vector<int> rightVin(vin.begin() + splitIndex + 1, vin.end());root->left = reConstructBinaryTree(leftPre, leftVin);root->right = reConstructBinaryTree(rightPre, rightVin);return root;}
};

📁 JZ26 树的子结构

        遍历第一个二叉树，检查每个节点是否是子结构。

        成立的第一个条件就是根节点值相同，如果不同，递归左右子树，检查是否存在子结构。

class Solution {
public:bool doseHave(TreeNode* root1, TreeNode* root2){if(root2 == nullptr)return true;if(root1 == nullptr)return false;if(root1->val != root2->val)return false;return doseHave(root1->left, root2->left) && doseHave(root1->right, root2->right);}bool HasSubtree(TreeNode* root1, TreeNode* root2) {bool ret = false;if(root1 == nullptr || root2 == nullptr)return false;if(root1->val == root2->val)ret = doseHave(root1, root2);if(!ret)ret = HasSubtree(root1->left, root2) || HasSubtree(root1->right, root2);return ret;}
};

📁 JZ33 二叉搜索树的后序遍历序列

        后序遍历中最后一个节点一定是根节点。

        左右子树划分：从左往右扫描，找到第一个大于根节点的值，作为左右子树分界点。分界点左侧为左子树（所有值 < 根节点），右侧为右子树（所有值 > 根节点）。

        检查右子树是否全部大于根节点，并递归验证左右子树是否满足二叉搜索树的条件。

class Solution {
public:bool VerifySquenceOfBST(vector<int> sequence) {if(sequence.empty())return false;return check(sequence,0, sequence.size() - 1);}bool check(vector<int>& seq, int begin, int end){if(begin >= end)return true;int root = seq[end];// 找分界点int i = begin;while(seq[i] < root)++i;int point = i;        // 检查右子树是否都大于根节点while(seq[i] > root)++i;// 在检查左右子树是否合法return (i == end)&& check(seq, begin, point - 1)&& check(seq, point, end - 1);}
};

📁 JZ82 二叉树中和为某一值的路径(一)

        递归到根节点，递归时删除当前层节点的值，递归到叶子节点时，判断是否与sum相等即可。

#include <functional>
class Solution {
public:bool hasPathSum(TreeNode* root, int sum) {if(root == nullptr)return false;if(!root->left && !root->right)return root->val == sum;return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum-root->val);}
};

📁 JZ34 二叉树中和为某一值的路径(二)

        相较于上一道题目，改为了记忆化搜索，即记录之前的路径即可。每一层节点保存在一个数组中，然后目标值-节点值。到叶子节点时，比较剩余值是否=叶子结点值。

        注意要返回上一层时，要把当前层节点的值从数组中移除。

#include <vector>
class Solution {
public:vector<vector<int>> ret;void dfs(TreeNode* root, int target, vector<int>& tmp){if(root == nullptr)return ;tmp.push_back(root->val);if(!root->left && !root->right){if(root->val == target)ret.push_back(tmp);tmp.pop_back();return ;}dfs(root->left, target - root->val, tmp);dfs(root->right, target - root->val, tmp);tmp.pop_back();}vector<vector<int> > FindPath(TreeNode* root, int target) {if(root == nullptr) return vector<vector<int>>();vector<int> tmp;dfs(root, target, tmp);return ret;}
};

📁  JZ84 二叉树中和为某一值的路径(三)

        相较于上面两道题，将起始节点节点固定在根节点，这道题目，就改变了一点，不固定起始节点。

        即路径可以从任意一个节点开始，采用 前序遍历，遍历每一个节点node，求从node节点出发，一共有多少条路径之和等于sum。然后再去左右子树查找即可。

class Solution {
public:int FindPath(TreeNode* root, int sum) {if(root == nullptr)return 0;int ret = 0;// 以当前节点为起点的路径ret += countRoute(root,sum);// 在计算以左右子树根节点为起点的路径ret += FindPath(root->left, sum);ret += FindPath(root->right, sum);return ret;}// 以root为起点的路径, 求有多少条路径之和等于sumint countRoute(TreeNode* root, int sum){if(!root)return 0;int ret = 0;if(root->val == sum)ret++;ret += countRoute(root->left, sum - root->val);ret += countRoute(root->right, sum - root->val);return ret;}
};

📁 JZ36 二叉搜索树与双向链表

        采用中序遍历+指针调整。在遍历过程中动态掉调整指针指向。

        左指针left --> 当前节点的前驱；右指针right --> 当前节点的后继。

1. ​​中序遍历递归框架​​：

   按“左子树 → 根 → 右子树”顺序访问节点，确保节点按值升序处理。

2. ​​维护前驱节点 prev​​：

   记录当前节点的前一个节点，用于双向链接。

3. ​​指针调整操作​​：

   • 若 prev非空：

     prev->right = current（前驱的后继指向当前节点）

     current->left = prev（当前的前驱指向前驱节点）

   • 若 prev为空：当前节点是链表头节点（中序遍历的第一个节点）。

4. ​​更新 prev​​：

   每处理完当前节点后，prev指向该节点，以便后续链接。

5. ​​返回头节点​​：

   链表头节点是中序遍历的第一个节点（即树的最左叶子节点）。

class Solution {
public:TreeNode* head = nullptr;	// 双向链表的头结点TreeNode* prev = nullptr;	// 前驱节点s// 中序遍历void inorder(TreeNode* cur){if(!cur)return ;inorder(cur->left);if(prev){prev->right = cur;	// 前驱节点的后继指针right指向当前节点cur->left = prev;	// 当前节点的前驱指针left 指向 前驱节点}else{// 找到头结点head = cur;}prev = cur;	// 更新当前节点为前驱节点inorder(cur->right);}TreeNode* Convert(TreeNode* root) {if(!root)return nullptr;inorder(root);return head;}
};

📁 JZ79 判断是不是平衡二叉树

        采用后序遍历+求二叉树深度的思路。比较左右子树的高度，如果 > 1，返回false。判断当前子树之前，先判断左右子树。

#include <ios>
class Solution {
public:int height(TreeNode* root){if(root == nullptr)return 0;return max(height(root->left),height(root->right)) + 1;}bool IsBalanced_Solution(TreeNode* pRoot) {if(pRoot == nullptr)return true;if(!IsBalanced_Solution(pRoot->left) || !IsBalanced_Solution(pRoot->right))return false;int leftH = height(pRoot->left);int rightH = height(pRoot->right);return abs(leftH-rightH) <= 1;}
};

📁 JZ28 对称的二叉树

        先序遍历，判断左右子树的根节点是否相等，如果不相等直接返回false；如果相等，判断左子树的左子树==右子树的右子树 并且 左子树的右子树=右子树的左子树。

class Solution {
public:bool dfs(TreeNode* left, TreeNode* right){if(!left && !right)return true;if(!left || !right)return false;if(left->val != right->val)return false;return dfs(left->left, right->right) && dfs(left->right, right->left);}bool isSymmetrical(TreeNode* pRoot) {if(pRoot == nullptr)return true;return dfs(pRoot->left, pRoot->right);}
};

📁 JZ8 二叉树的下一个结点

        中序遍历：左子树，根节点，右子树的顺序遍历。现在我们要按照中序遍历返回下一个节点，即根节点的下一个节点，分析两种情况即可。

1. 右子树存在：

        返回右子树的最左侧节点。     

2. 右子树不存在：

        说明当前子树已经遍历完毕，向上返回。判断当前子树是根节点父亲节点的左右子树。

        (1). 当前子树是右子树：说明父亲节点所在子树已经遍历完毕，再向上查找，直到找到一颗还没有遍历的节点。

        (2). 当前子树是左子树：说明父节点还没有遍历，返回

class Solution {
public:TreeLinkNode* GetNext(TreeLinkNode* node) {if(node == nullptr)return nullptr;// 如果存在右子树 结果就是右子树的最左侧节点if(node->right){TreeLinkNode* ret = node->right;while(ret->left)ret = ret->left;return ret;}// 向上找一个右子树不为node的父亲节点 while(node->next && node->next->right == node){node = node->next;}return node->next;}
};

📁 JZ78 把二叉树打印成多行

        层序遍历：利用队列，将每层结果保存在一维数组中。遍历完一层后，将一维数组插入的二维数组中。

#include <vector>
class Solution {
public:vector<vector<int> > Print(TreeNode* root) {if(root == nullptr)return vector<vector<int>>();vector<vector<int>> ret;queue<TreeNode*> q;q.push(root);while(!q.empty()){int sz = q.size();vector<int> tmp;for(int i = 0 ; i < sz ; ++i){TreeNode* node = q.front();q.pop();tmp.push_back(node->val);if(node->left)q.push(node->left);if(node->right)q.push(node->right);}ret.push_back(tmp);}return ret;}
};

📁 JZ86 在二叉树中找到两个节点的最近公共祖先

定义一个递归函数。目的是查找最近的公共最先节点。有两种情况：

1. 两个节点在不同的两侧，存在一个祖先节点。

2. 两个节点在同一侧，说明其中一个节点一定是祖先节点。

        根据上面的思路，判断即可。检查当前节点是否是要查找的节点；检查要查找的两个节点是两种情况的哪一种情况。

        i.  如果是第一种情况，直接返回该节点即可；

        ii. 如果是第二种情况，此时返回左右子树递归的结果（递归直接返回最上层的节点）。

        因为我们定义了，递归函数的返回值是最近的祖先节点。

#include <ios>
class Solution {
public:TreeNode* dfs(TreeNode* root, int o1 , int o2){if(root == nullptr)return nullptr;if(root->val == o1 || root->val == o2)return root;TreeNode* leftHave = dfs(root->left, o1, o2);TreeNode* rightHave = dfs(root->right, o1, o2);if(leftHave && rightHave)return root;return leftHave ? leftHave : rightHave;}int lowestCommonAncestor(TreeNode* root, int o1, int o2) {return dfs(root, o1, o2)->val;}
};

📁 JZ68 二叉搜索树的最近公共祖先

        解法上一题一样。

#include <ios>
class Solution {
public: TreeNode* dfs(TreeNode* root, int p, int q){if(root == nullptr)return root;if(root->val == p || root->val == q)return root;TreeNode* leftHave = dfs(root->left, p, q);TreeNode* rightHave = dfs(root->right, p, q);if(leftHave && rightHave)return root;return leftHave ? leftHave : rightHave;}int lowestCommonAncestor(TreeNode* root, int p, int q) {return dfs(root, p, q)->val;}
};