企业官网建设流程全解析

1

如何计算二叉树的节点个数???

第一种就是设计一个全局变量来记录节点

第二种就是用递归的思想

方法一：全局变量计数

思路：定义全局变量gsize，递归遍历二叉树，每访问到一个有效节点，计数 + 1。

int gsize = 0; void TreeSize1(BTNode* root) { if (root == NULL) { return; } gsize++; TreeSize1(root->left); TreeSize1(root->right); }

缺点：

1. 全局变量有状态残留，多次调用必须手动清零，非常容易出错；
2. 如果多棵树同时统计，全局变量会互相干扰；

方法二：分治递归

递归思想：当前树节点数 = 1（自己） + 左子树节点数量 + 右子树节点数量

int TreeSize2(BTNode* root) { if (root == NULL) { return 0; } return 1 + TreeSize2(root->left) + TreeSize2(root->right); }

优点：

1. 无全局变量，无残留状态，每次调用独立计算；
2. 代码简洁，符合分治思想，面试最推荐写法；
3. 不用手动清零，不会多次调用叠加。

2.

104. 二叉树的最大深度 - 力扣（LeetCode）

题目描述

给定二叉树根节点root，求二叉树的最大深度。

二叉树的深度：从根节点到最远叶子节点的最长路径上的节点数量。 叶子节点：左右孩子都为NULL的节点。

递归思路（分治思想，和前面统计节点数是一套递归范式）

一棵二叉树的最大深度 =1（当前节点） + max(左子树深度，右子树深度)

• 递归终止条件：root == NULL，空树深度为 0
• 先求左子树深度，再求右子树深度，取两者较大值，再加当前节点的 1

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int maxDepth(TreeNode* root) { if(root==NULL) return 0; return 1+fmax(maxDepth(root->left),maxDepth(root->right)); } };

3

98. 验证二叉搜索树 - 力扣（LeetCode）

题目描述

你需要采用前序遍历的方式，将一个二叉树转换成一个由括号和整数组成的字符串。

空节点则用一对空括号()表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

规则总结：

1. 节点没有左右孩子：只输出节点值，不加任何括号
2. 节点只有左孩子：左子树加括号，右子树的 () 省略
3. 节点只有右孩子：左子树必须保留()，右子树加括号，不能省略！
4. 左右都有孩子：左右子树都加括号

思路分析

采用前序遍历（根 → 左 → 右）：

1. 先拼接当前节点的值
2. 如果是叶子节点（左右都空），直接返回，不添加括号
3. 处理左子树：无论左子树是否为空，都先加(递归左子树，再加)
   • 若左子树为空，递归进去直接返回空字符串，就会生成()，正好满足【只有右孩子时左括号不能省略】的要求
4. 判断：左不为空、右为空，直接 return，省略右子树括号
5. 否则处理右子树：拼接(递归右子树，拼接)

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool isValidBST(TreeNode* root) { } };

4

98. 验证二叉搜索树 - 力扣（LeetCode）

题目描述

给你一个二叉树的根节点root，判断其是否是一个有效的二叉搜索树。

二叉搜索树 BST 的定义：

1. 节点左子树所有节点的值严格小于当前节点的值；
2. 节点右子树所有节点的值严格大于当前节点的值；
3. 左右子树也必须是二叉搜索树。

✨ 核心性质：二叉搜索树的中序遍历序列一定是严格递增的！利用这个特性，我们只需要做中序遍历，记录上一个访问到的值，保证后访问的值 > 前一个值即可。

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: long long prev=LLONG_MIN; bool isValidBST(TreeNode* root) { if(root==nullptr) return true; if(!isValidBST(root->left)) return false; if(root->val<=prev) return false; prev=root->val; if(!isValidBST(root->right)) return false; return true; } };

5

100. 相同的树 - 力扣（LeetCode）100. 相同的树 - 给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。 示例 1：[https://assets.leetcode.com/uploads/2020/12/20/ex1.jpg]输入：p = [1,2,3], q = [1,2,3]输出：true示例 2：[https://assets.leetcode.com/uploads/2020/12/20/ex2.jpg]输入：p = [1,2], q = [1,null,2]输出：false示例 3：[https://assets.leetcode.com/uploads/2020/12/20/ex3.jpg]输入：p = [1,2,1], q = [1,1,2]输出：false 提示： * 两棵树上的节点数目都在范围 [0, 100] 内 * -104 <= Node.val <= 104https://leetcode.cn/problems/same-tree/

题目描述

给你两棵二叉树的根节点p和q，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

判断两个树相同两个条件：

1. 结构完全一样：对应位置同时存在节点，或者同时为空
2. 对应节点的值相等

递归思路：同时遍历两棵树，一对一对对比节点

1. 终止条件 1：p == NULL && q == NULL。两个节点同时为空 → 当前位置完全一致，返回 true
2. 终止条件 2：一个空、一个不为空，结构不一样，直接返回 false
3. 两个节点都不为空：判断节点值，如果值不相等，返回 false
4. 递归对比左子树，左子树不相同直接返回 false
5. 递归对比右子树，右子树不相同直接返回 false
6. 左右子树全部匹配成功，返回 true

遍历顺序：根节点判断 → 左子树递归 → 右子树递归，属于前序遍历。

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), * right(right) {} * }; */ class Solution { public: bool isSameTree(TreeNode* p, TreeNode* q) { if(p==NULL&&q==NULL) return true; if(p==NULL&&q!=NULL) return false; if(p!=NULL&&q==NULL) return false; if(p->val!=q->val) return false; if(!isSameTree(p->left,q->left)) return false; if(!isSameTree(p->right,q->right)) return false; return true; } };

6.

572. 另一棵树的子树 - 力扣（LeetCode）

题目描述

给你两棵二叉树root和subRoot。检验root中是否包含和subRoot具有相同结构和节点值的子树。 一棵二叉树的子树包括某个节点和这个节点所有后代节点。

关键点：

1. 子树必须是从某个节点往下全部完全匹配，不能只匹配一部分；
2. 子树是原树的某个节点，连同它全部后代构成的树；
3. 复用我们上一题写的isSameTree（判断两棵树完全相同）。

思路拆解

核心思想

1. 辅助函数isSameTree(p,q)：判断两棵树结构 + 节点值完全一模一样（LeetCode100 原题）
2. isSubtree递归逻辑：
   • 递归终止：root == nullptr，空树不可能包含子树，直接返回false
   • 检查当前根节点出发，是否和 subRoot 完全相同，相同直接返回 true
   • 如果当前节点不匹配：去左子树或者右子树继续查找，只要一边找到就返回 true

||是短路求值：左子树找到了，就不会再递归右子树，提前返回。

class Solution { public: bool isSameTree(TreeNode* p, TreeNode* q) { if (p == nullptr && q == nullptr) return true; if (p == nullptr || q == nullptr) return false; if (p->val != q->val) return false; return isSameTree(p->left, q->left) && isSameTree(p->right, q->right); } bool isSubtree(TreeNode* root, TreeNode* subRoot) { if (root == nullptr) return false; // 关键：先判空 if (isSameTree(root, subRoot)) return true; return isSubtree(root->left, subRoot) || isSubtree(root->right, subRoot); } };