1如何计算二叉树的节点个数???第一种就是设计一个全局变量来记录节点第二种就是用递归的思想方法一全局变量计数思路定义全局变量gsize递归遍历二叉树每访问到一个有效节点计数 1。int gsize 0; void TreeSize1(BTNode* root) { if (root NULL) { return; } gsize; TreeSize1(root-left); TreeSize1(root-right); }缺点全局变量有状态残留多次调用必须手动清零非常容易出错如果多棵树同时统计全局变量会互相干扰方法二分治递归递归思想当前树节点数 1自己 左子树节点数量 右子树节点数量int TreeSize2(BTNode* root) { if (root NULL) { return 0; } return 1 TreeSize2(root-left) TreeSize2(root-right); }优点无全局变量无残留状态每次调用独立计算代码简洁符合分治思想面试最推荐写法不用手动清零不会多次调用叠加。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(rootNULL) return 0; return 1fmax(maxDepth(root-left),maxDepth(root-right)); } };398. 验证二叉搜索树 - 力扣LeetCode题目描述你需要采用前序遍历的方式将一个二叉树转换成一个由括号和整数组成的字符串。空节点则用一对空括号()表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。规则总结节点没有左右孩子只输出节点值不加任何括号节点只有左孩子左子树加括号右子树的 () 省略节点只有右孩子左子树必须保留()右子树加括号不能省略左右都有孩子左右子树都加括号思路分析采用前序遍历根 → 左 → 右先拼接当前节点的值如果是叶子节点左右都空直接返回不添加括号处理左子树无论左子树是否为空都先加(递归左子树再加)若左子树为空递归进去直接返回空字符串就会生成()正好满足【只有右孩子时左括号不能省略】的要求判断左不为空、右为空直接 return省略右子树括号否则处理右子树拼接(递归右子树拼接)/** * 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) { } };498. 验证二叉搜索树 - 力扣LeetCode题目描述给你一个二叉树的根节点root判断其是否是一个有效的二叉搜索树。二叉搜索树 BST 的定义节点左子树所有节点的值严格小于当前节点的值节点右子树所有节点的值严格大于当前节点的值左右子树也必须是二叉搜索树。✨ 核心性质二叉搜索树的中序遍历序列一定是严格递增的利用这个特性我们只需要做中序遍历记录上一个访问到的值保证后访问的值 前一个值即可。/** * 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 prevLLONG_MIN; bool isValidBST(TreeNode* root) { if(rootnullptr) return true; if(!isValidBST(root-left)) return false; if(root-valprev) return false; prevroot-val; if(!isValidBST(root-right)) return false; return true; } };5100. 相同的树 - 力扣LeetCode100. 相同的树 - 给你两棵二叉树的根节点 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编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同并且节点具有相同的值则认为它们是相同的。判断两个树相同两个条件结构完全一样对应位置同时存在节点或者同时为空对应节点的值相等递归思路同时遍历两棵树一对一对对比节点终止条件 1p NULL q NULL。两个节点同时为空 → 当前位置完全一致返回 true终止条件 2一个空、一个不为空结构不一样直接返回 false两个节点都不为空判断节点值如果值不相等返回 false递归对比左子树左子树不相同直接返回 false递归对比右子树右子树不相同直接返回 false左右子树全部匹配成功返回 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(pNULLqNULL) return true; if(pNULLq!NULL) return false; if(p!NULLqNULL) 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具有相同结构和节点值的子树。 一棵二叉树的子树包括某个节点和这个节点所有后代节点。关键点子树必须是从某个节点往下全部完全匹配不能只匹配一部分子树是原树的某个节点连同它全部后代构成的树复用我们上一题写的isSameTree判断两棵树完全相同。思路拆解核心思想辅助函数isSameTree(p,q)判断两棵树结构 节点值完全一模一样LeetCode100 原题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); } };