国外域名查询_青海网页设计制作_最好的优化公司_搜索引擎网站优化和推广方案

前言

在二叉树的题目中，递归的解法无疑是是最简单和最好理解的，也能快速解题，本篇介绍一下递归的常见的二叉树题目。

 

题目链接

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

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

一、翻转二叉树

主要思路:从根节点出发，依次交换一下左右两边，即可解决题目。

TreeNode* invertTree(TreeNode* root) {if (root == NULL) return root;swap(root->left, root->right);  // 中invertTree(root->left);         // 左invertTree(root->right);        // 右return root;}

二、对称二叉树

思路：递归调用，层层判断，是否相等即可。

bool isSymmetric(TreeNode* root) {return root==nullptr||recur(root->left,root->right);}
private:bool recur(TreeNode* L, TreeNode* R) {if (L == nullptr && R == nullptr) return true;if (L == nullptr || R == nullptr || L->val != R->val) return false;return recur(L->left, R->right) && recur(L->right, R->left);}

 

三、最大深度

思路：分为左边和右边的最大深度比较一下即可。最后加上根节点。

int maxDepth(TreeNode* root) {if (root == nullptr) return 0;return max(maxDepth(root->left), maxDepth(root->right)) + 1;}

四、最小深度

思路：和上一个题一样，加了提前结束的判断条件。

int minDepth(TreeNode* root) {if (root == nullptr) return 0;if (root->left == nullptr && root->right == nullptr) return 1;if (root->left == nullptr) return minDepth(root->right) + 1;if (root->right == nullptr) return minDepth(root->left) + 1;return min(minDepth(root->left), minDepth(root->right)) + 1;}