最近在做LeetCode上面有关二叉树的题目，这篇博客仅用来记录这些题目的代码。
二叉树的题目，一般都是利用递归来解决的，因此这一类题目对理解递归很有帮助。
1.Symmetric Tree（https://leetcode.com/problems/symmetric-tree/description/）
class Solution {
public:
bool isSymmetric(TreeNode* root) {
return root == NULL || isMirror(root->left, root->right);
}
bool isMirror(TreeNode *left, TreeNode *right) {
if (left == NULL && right == NULL) return true;
if (left == NULL || right == NULL) return false;
if (left->val != right->val) return false;
return isMirror(left->left, right->right) && isMirror(left->right, right->left);
}
};
2.Binary Tree Level Order Traversal（https://leetcode.com/problems/binary-tree-level-order-traversal/description/）
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if (root == NULL) return res;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int layer_size = q.size();
vector<int> layer;
for (int i = ; i < layer_size; i++) {
TreeNode *temp = q.front();
q.pop();
layer.push_back(temp->val);
if (temp->left != NULL) q.push(temp->left);
if (temp->right != NULL) q.push(temp->right)；
} }
return res;
}
};
3.Binary Tree Level Order Traversal II（https://leetcode.com/problems/binary-tree-level-order-traversal-ii/description/）
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> res;
if (root == NULL) return res;
vector<int> layer;
queue<TreeNode*> q;
q.push(root);
int count = ;
while (!q.empty()) {
TreeNode* temp = q.front();
q.pop();
count--;
layer.push_back(temp->val);
if (temp->left != NULL) q.push(temp->left);
if (temp->right != NULL) q.push(temp->right);
if (count == ) {
count = q.size();
res.push_back(layer);
layer.clear();
}
}
for (int i = ; i < res.size() / ; i++) {
vector<int> temp = res[i];
res[i] = res[res.size() - i - ];
res[res.size() - i - ] = temp;
}
return res;
}
};
4.Same Tree（https://leetcode.com/problems/same-tree/description/）
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if (p == NULL && q == NULL) return true;
if (p == NULL || q == NULL) return false;
if (p->val != q->val) return false;
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
};
5.Path Sum（https://leetcode.com/problems/path-sum/description/）
class Solution {
public:
bool hasPathSum(TreeNode* root, int sum) {
if (root == NULL) return false;
if (root->left == NULL && root->right == NULL && sum == root->val) return true;
else return hasPathSum(root->left, sum - root->val) || hasPathSum(root->right, sum - root->val);
}
};
6.Path Sum II（https://leetcode.com/problems/path-sum-ii/description/）
class Solution {
public:
void helper(TreeNode *root, vector<vector<int>>& res, vector<int> t, int sum) {
if (root == NULL) return;
if (sum - root->val == && root->left == NULL && root->right == NULL) {
t.push_back(root->val);
res.push_back(t);
}
else if (root->left == NULL && root->right == NULL) {
return;
}
else {
t.push_back(root->val);
helper(root->left, res, t, sum - root->val);
helper(root->right, res, t, sum - root->val);
}
}
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<vector<int>> res;
if (root == NULL) return res;
vector<int> t;
helper(root, res, t, sum);
return res;
}};
7.Sum Root to Leaf Numbers（https://leetcode.com/problems/sum-root-to-leaf-numbers/description/）
class Solution {
public:
int sumNumbers(TreeNode* root) {
return helper(root, );
}
int helper(TreeNode *root, int sum) {
if (root == NULL) return ;
if (root->left == NULL && root->right == NULL) return sum * + root->val;
else return helper(root->left, sum * + root->val ) + helper(root->right, sum * + root->val);
}
};
8.Binary Tree Right Side View（https://leetcode.com/problems/binary-tree-right-side-view/description/）
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
vector<int> res;
if (root == NULL) return res;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
for (int i = ; i < size; i++) {
TreeNode * temp = q.front();
q.pop();
if (temp->left) q.push(temp->left);
if (temp->right) q.push(temp->right);
if (i == size - ) {
res.push_back(temp->val);
}
}
}
return res;
}
};
9.Maximum Depth of Binary Tree（https://leetcode.com/problems/maximum-depth-of-binary-tree/description/）
递归解法：
class Solution {
public:
int maxDepth(TreeNode* root) {
if (root == NULL) return ;
if (root->left == NULL && root->right == NULL) return ;
int maxl = maxDepth(root->left);
int maxr = maxDepth(root->right);
return maxl > maxr ? maxl + : maxr + ;
}
};
BFS解法：
class Solution {
public:
int maxDepth(TreeNode* root) {
int res = ;
if (root == NULL) return ;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int size = q.size();
for (int i = ; i < size; i++) {
TreeNode* temp = q.front();
q.pop();
if (temp->left) q.push(temp->left);
if (temp->right) q.push(temp->right);
}
res++;
}
return res;
}
};
10.Binary Tree Inorder Traversal(https://leetcode.com/problems/binary-tree-inorder-traversal/description/)
普通的中序遍历。
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> res;
inOrder(res, root);
return res;
}
void inOrder(vector<int>& inorder, TreeNode *root) {
if (root == NULL) return;
inOrder(inorder, root->left);
inorder.push_back(root->val);
inOrder(inorder, root->right);
}
};
11.Validate Binary Search（https://leetcode.com/problems/validate-binary-search-tree/）
判断一棵二叉树是否二叉搜索树。
class Solution {
public:
bool isValidBST(TreeNode* root) {
if (root == NULL) return true;
vector<int> seq;
inOrder(seq, root);
for (int i = ; i < seq.size() - ; i++) {
if (seq[i] >= seq[i + ]) return false;
}
return true;
}
void inOrder(vector<int> &seq, TreeNode *root) {
if (root == NULL) return;
else {
inOrder(seq, root->left);
seq.push_back(root->val);
inOrder(seq, root->right);
}
}
};
12.Convert Sorted Array to Binary Search Tree（https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/description/）
使用分治法。
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
return BSTNode(nums, , nums.size() - );
}
TreeNode* BSTNode(vector<int> &nums, int first, int last) {
if (first > last) return NULL;
else {
int mid = (first + last) / ;
TreeNode *root = new TreeNode(nums[mid]);
root->left = BSTNode(nums, first, mid - );
root->right = BSTNode(nums, mid + , last);
return root;
} }
};
13.Balanced Binary Tree（https://leetcode.com/problems/balanced-binary-tree/description/）
判断一棵二叉树是否平衡二叉树。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isBalanced(TreeNode* root) {
int depth = ;
return isBalanced(root, depth);
}
bool isBalanced(TreeNode* root, int &depth) {
if (root == NULL) {
depth = ;
return true;
}
else {
int LeftDepth;
int RightDepth;
bool isLeftBalanced = isBalanced(root->left, LeftDepth);
bool isRightBalanced = isBalanced(root->right, RightDepth);
if (isLeftBalanced && isRightBalanced) {
if (abs(LeftDepth - RightDepth) <= ) {
depth = LeftDepth > RightDepth ? LeftDepth + : RightDepth + ;
return true;
} }
return false;
}
}
};
