100. 相同的树
/**
* 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 isSameTree(TreeNode* p, TreeNode* q) {
if (p == nullptr && q == nullptr) {
return true;
}
if (p != nullptr && q != nullptr && p->val == q->val) {
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
} else {
return false;
}
}
};
101. 对称二叉树
/**
* 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 isSymmetric(TreeNode* root) {
return ismirror(root, root);
}
bool ismirror(TreeNode* p, TreeNode* q) {
if (p == NULL && q == NULL) {
return true;
}
if (p == NULL || q == NULL) {
return false;
}
if (p->val == q->val) {
return ismirror(p->left, q->right) && ismirror(p->right, q->left);
} else {
return false;
}
}
};
102. 二叉树的层次遍历
/**
* 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:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
if (!root)
return res;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
vector<int> tmp;
int len = q.size(); // 当前层的节点的数目
for (int i = 0; i < len; i++) {
TreeNode* node = q.front();
q.pop();
tmp.push_back(node->val);
if (node->left)
q.push(node->left);
if (node->right)
q.push(node->right);
}
res.push_back(tmp);
}
return res;
}
};
103. 二叉树的锯齿形层次遍历
/**
* 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:
vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
vector<vector<int>> res;
if (!root)
return res;
queue<TreeNode*> q;
int zig_flag = 0;
q.push(root);
while (!q.empty()) {
int len = q.size();
vector<int> tmp;
for(int i = 0; i < len; i++) {
TreeNode* node = q.front();
q.pop();
tmp.push_back(node->val);
if(node->left)
q.push(node->left);
if(node->right)
q.push(node->right);
}
if(zig_flag % 2 == 1)
reverse(tmp.begin(), tmp.end());
res.push_back(tmp);
zig_flag++;
}
return res;
}
};
104. 二叉树的最大深度
/**
* 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:
int maxDepth(TreeNode* root) {
if(!root)
return 0;
return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}
};
面试题 17.12. BiNode
/**
* 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:
TreeNode* convertBiNode(TreeNode* root) {
// 中旭遍历，左根右
if (!root)
return root;
// init stack，左子树优先
stack<TreeNode*> s;
while (root) {
s.push(root);
root = root->left;
}
TreeNode* head = s.top();
while (!s.empty()) {
TreeNode* leftNode = s.top();
s.pop();
TreeNode* node = leftNode->right;
while(node) { // 左子树优先
s.push(node);
node = node->left;
}
leftNode->left = nullptr;
leftNode->right = s.empty() ? nullptr : s.top();
}
return head;
}
};
面试题68 - II. 二叉树的最近公共祖先
/**
* 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:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
// 到达末端或者访问到 p 或 q 时结束递归
if(!root || root == p || root == q) {
return root;
}
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
//p, q 一个在左子树，一个在右子树
if (left != nullptr && right != nullptr)
return root;
// p, q 都在左子树
if (left != nullptr)
return left;
// p, q 都在右子树
if (right != nullptr)
return right;
return nullptr;
}
};
面试题68 - I. 二叉搜索树的最近公共祖先
二叉搜索树者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉搜索树。
/**
* 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:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
// 注意题目要求是二叉搜索树
if (root == nullptr)
return nullptr;
if (root->val > p->val && root->val > q->val)
return lowestCommonAncestor(root->left, p, q);
if (root->val < p->val && root->val < q->val)
return lowestCommonAncestor(root->right, p, q);
return root;
}
};
网友评论