引言226. 翻转二叉树 - 力扣LeetCode101. 对称二叉树 - 力扣LeetCode110. 平衡二叉树 - 力扣LeetCode257. 二叉树的所有路径 - 力扣LeetCode404. 左叶子之和 - 力扣LeetCode222. 完全二叉树的节点个数 - 力扣LeetCode第一题每一次写二叉树的题目我们一定要确定两个事情第一个是非递归还是递归第二个是什么遍历顺序。这一题我们选择的是前序遍历最好不要选择中序遍历。首先我们交换结点是左右子树交换也就是说我们的中间这个结点要么是在最开始交换前序要么是在最后面交换后序。如果是最开始交换那么就相当于先确定这个子树的位置是在左边还是在右边然后调整子树的细节如果是在最后面交换那么就相当于先把细节调整好最后确定这个子树是在左边还是右边。但是如果是中序遍历我们先把左边放到了右边然后把整个子树交换了然后你又一次操作了右子树也就是原来的左子树对着同一个树操作了两边肯定是错的。所以如果要选择中序遍历必须两次都是invertTree(root-left)。其实本质上可以想象成一个根节点和两个子树我们invertTree(root-left)就是把左子树调整好了invertTree(root-right)就是把右子树调整好了而swap(root-left,root-right)就是把这两个子树交换一下所以swap的位置就决定了我们到底是调整的原本的哪个子树/** * 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: TreeNode* invertTree(TreeNode* root) { if (root nullptr) { return nullptr; } swap(root-left, root-right); invertTree(root-left); invertTree(root-right); return root; } };第二题这一题我们选择的是后序遍历原因就是我们判断两个结点是不是对称的前提就是这两个结点的子树对不对称而后序遍历就是可以帮助结点收集左右孩子的信息。首先我们代码先是判断这个结点是不是和对称的。可能大家有疑惑就是这个不是前序遍历的操作吗emmm确实是有点像但是这个并不是我们的操作你可以把这个理解成对每个遍历结点的一个标记如果返回true就继续往下遍历收集孩子们的信息如果返回false就说明这个结点根本就不对称根本不需要收集孩子的信息了直接原地返回。后面的代码就是收集信息的过程了也就是后续遍历的基本操作。这一题之所以不用原来题目里面自己给的函数是因为我们需要比较而这个比较的过程是两个树一起进行的所以我们必须提供left和right两个子树如果只提供一个root很难做到两个子树一起遍历比较。/** * 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 compare(TreeNode* left, TreeNode* right) { if (left nullptr right ! nullptr) { return false; } else if (left ! nullptr right nullptr) { return false; } else if (left nullptr right nullptr) { return true; } else if (left-val ! right-val) { return false; } bool res1 compare(left-left, right-right); bool res2 compare(left-right, right-left); bool res res1 res2; return res; } bool isSymmetric(TreeNode* root) { if (root nullptr) { return true; } return compare(root-left, root-right); } };第三题这一题主要解决的问题就是判断这个树是不是平衡树。我们求树的高度时我们会在传参的时候我们会多传一个depth这个参数的意义就是记录每一个结点的高度这样子在每一个回溯的过程中都可以知道现在的depth是什么 。而这一题我们需要换一个思路我们用递归来写首先如果我们递归到空姐点之后就返回0方便后面的计算如果不是空结点那么我们先向左再向右同时也要判断一下这个返回值是不是-1如果是-1说明已经不平衡了那么我们要把这个返回值一个一个的往上传递传到根节点最后我们接受如果平衡那么我们就取左右最大的一个值并加上这个结点的1即1 max(leftHight rightHight)。所以我们的思路还是很清晰的主要是后序遍历所以我们处理结点的高度也是放在最后因为一个结点的高度是取决于它的子树的只有把结点的子树全部遍历结束才可以知道这个结点的高度所以这正好符合我们的正序遍历/** * 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 findH(TreeNode* node) { if (node-nullptr) { return 0; } int leftHight findH(node-left); if (leftHight -1) { return -1; } int rightHight findH(node-right); if (rightHight -1) { return -1; } return abs(leftHight - rightHight) 1 ? -1 : 1 max(leftHight rightHight); } bool isBalanced(TreeNode* root) { if (findH(root) -1) { return false; } else { return true; } } };第四题这一题涉及到了回溯的思想也就是深搜然后记录路径结点。不过这一题的难题不在于此在于返回的是字符串中间要加上-所以我们到叶子节点之后我们还要单独处理一下这个问题我们定义一个新的spath然后把path全部搬移到这里面来并且在中间加上-不过一定要注意的是最后一个没有-所以在我们遍历的时候我们需要单独处理最后一个元素。这里还有一个思考的问题我们这里的传参是拷贝传参也就是vectorint path这个就需要我们手动回溯但是如果我们是传值vectorint path我们就不需要手动回溯了因为这个值是在栈中不会被我们传递下去的。所以不同的传参方式决定了不同的写法。/** * 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: vectorstring res; void backtracing(TreeNode* cur, vectorint path) { path.push_back(cur-val); if (cur-left nullptr cur-right nullptr) { string spath; for (int i 0; i path.size() - 1; i) { spath to_string(path[i]); spath -; } spath to_string(path[path.size() - 1]); res.push_back(spath); return; } if (cur-left) { backtracing(cur-left, path); path.pop_back(); } if (cur-right) { backtracing(cur-right, path); path.pop_back(); } } vectorstring binaryTreePaths(TreeNode* root) { vectorint path; if (root nullptr) { return res; } backtracing(root, path); return res; } };第五题对于左子叶的处理是统一的所以不管是先往右边遍历还是往左边遍历我们最后统计的操作都是那一个最后我们需要把这两个方向的值相加即可然后把这个值向上传递最后一层一层的传递到根节点。/** * 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 sumOfLeftLeaves(TreeNode* root) { if (root nullptr) { return 0; } int leftSum sumOfLeftLeaves(root-left); if (root-left root-left-left nullptr root-left-right nullptr) { leftSum root-left-val; } int rightSum sumOfLeftLeaves(root-right); int sum leftSum rightSum; return sum; } };第六题我觉得这一题很考验对于递归的理解。首先我们计算完全二叉树如果用层序遍历是非常麻烦的而递归的思想主要就是不停的细分如果一颗大的二叉树是完全二叉树我们直接用公式计算就可以但是如果是不是那么我们就接着往下分直到小到只有一个结点单独一个结点也是一个完全二叉树。所以代码里面有两个出口一个是如果大的二叉树就是完全二叉树那么我们直接用公式计算然后返回如果不是那么我们继续往下递归总会碰上一颗完全二叉树的那个时候再用公式然后不断地向上传递只不过这个时候是左边的和右边的相加再加上本身的结点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 countNodes(TreeNode* root) { if (root nullptr) { return 0; } TreeNode* left root-left; TreeNode* right root-right; int leftDepth 0; int rightDepth 0; while(left) { left left-left; leftDepth; } while(right) { right right-right; rightDepth; } if (leftDepth rightDepth) { return (2 leftDepth) - 1; } return countNodes(root-left) countNodes(root-right) 1; } };总结递归的思路并不是很好想因为涉及到处理节点遍历顺序出口等等这种是需要很多很多题目的积累的。本篇文章到这里就结束了希望可以帮助到大家理解~~~