算法（二叉树递归）-尧图网络科技

引言

226. 翻转二叉树 - 力扣（LeetCode）

101. 对称二叉树 - 力扣（LeetCode）

110. 平衡二叉树 - 力扣（LeetCode）

257. 二叉树的所有路径 - 力扣（LeetCode）

404. 左叶子之和 - 力扣（LeetCode）

222. 完全二叉树的节点个数 - 力扣（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全部搬移到这里面来并且在中间加上->，不过一定要注意的是最后一个没有->，所以在我们遍历的时候，我们需要单独处理最后一个元素。

这里还有一个思考的问题，我们这里的传参是拷贝传参，也就是vector<int>& path，这个就需要我们手动回溯，但是如果我们是传值vector<int> 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: vector<string> res; void backtracing(TreeNode* cur, vector<int>& 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(); } } vector<string> binaryTreePaths(TreeNode* root) { vector<int> 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; } };