二叉树
226.翻转二叉树
Tag: 二叉树,广度优先搜索,深度优先搜索
题目
https://leetcode.cn/problems/invert-binary-tree/
Solution1
遍历二叉树,递归翻转
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
|
class Solution { public: TreeNode* invertTree(TreeNode* root) { if (root == nullptr) { return nullptr; }
TreeNode *tmp = root->left; root->left = invertTree(root->right); root->right = invertTree(tmp);
return root; } };
|
101.对称二叉树
Tags: 二叉树,广度优先搜索,深度优先搜索
题目
https://leetcode.cn/problems/symmetric-tree/
Solution1
深度优先搜索,递归判断
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
|
bool dfs(TreeNode *left, TreeNode *right) { if (left == nullptr || right == nullptr) { return ((left == nullptr) && (right == nullptr)); }
if (left->val != right->val) { return false; }
return dfs(left->left, right->right) && dfs(left->right, right->left); }
class Solution { public: bool isSymmetric(TreeNode* root) { if (root == nullptr) return true;
return dfs(root->left, root->right); } };
|
-
优点:简洁易懂
-
缺点:没啥缺点,但是递归。可以优化为尾递归
-
结论:好办法
链表
92.反转链表 II
Tags: 链表
题目
https://leetcode.cn/problems/reverse-linked-list-ii/
Solution1