经典题的经典解法总结
背景
我见过许多优秀的题目的经典解法，很是佩服，同时也提高了自己的知识水平。这些解法的特点是简单，有些已经到了减无可减的地步。 我个人认为，对于这种，我们只能膜拜 + 硬背了，本篇博客就打算整理这些经典题的经典解法，以供大家学习。
第一题 求二叉树的高度
// 时间复杂度O(n)，空间复杂度O(logn)
class Solution {
int maxDepth(TreeNode root) {
if (root == null) return 0;
return max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
};
第二题 判断二叉树是否镜像对称
// 递归版，时间复杂度O(n)，空间复杂度O(logn)
class Solution {
bool isSymmetric(TreeNode root) {
return root ? isSymmetric(root.left, root.right) : true;
}
bool isSymmetric(TreeNode left, TreeNode right) {
if (!left && !right) return true; // 终止条件
if (!left || !right) return false; // 终止条件
return left.val == right.val // 三方合并
&& isSymmetric(left.left, right.right)
&& isSymmetric(left.right, right.left);
}
};
第三题 只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次外，其余每个元素均出现两次，找出那个只出现一次的元素
// 时间复杂度O(n)，空间复杂度O(1)
class Solution {
int singleNumber(int A[], int n) {
int x = 0;
for (int i = 0; i < n; ++i)
x ^= A[i];
return x;
}
};
