树
- 二叉查找树
- 树的遍历
- 平衡树
树的高度
111. Minimum Depth of Binary Tree
求树的最短深度（叶子节点到根的最小距离） 注意此题子树深度为0时，并没有叶子节点，要特殊处理 另外一种做法是层序遍历，用队列的结构，根据size或者每层push一个特殊node来判断层数。直到遇到一个叶子节点。 层序遍历比深度优先的递归更效率些。因为它不用查到最后一层
/**
* 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 minDepth(TreeNode* root) {
if(root == NULL){
return 0;
}
int left = minDepth(root->left);
int right = minDepth(root->right);
return ((left < right && left != 0) || right == 0) ? (left + 1) : (right + 1);
}
};
110. Balanced Binary Tree
判断是不是平衡树。注意不要重复调用 高度函数。 可以用-1 把不平衡的信息向上传递
/**
* 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) {
if(b(root) >= 0){
return true;
}else{
return false;
}
}
int b(TreeNode* root){
if(root == NULL){
return 0;
}
int l = b(root->left);
int r = b(root->right);
if(l < 0 || r <0){
return -1;
}
if(abs(l - r) > 1){
return - 1;
}
return max(l,r) + 1;
}
};
树的各种遍历
- 中序
/**
* 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<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> s;
vector<int> result;
TreeNode * cur = root;
while(cur || !s.empty()){
while(cur){
s.push(cur);
cur = cur->left;
}
TreeNode * tmp = s.top();
s.pop();
result.push_back(tmp->val);
cur = tmp->right;
}
return result;
}
};
- 前序遍历。 和上面类似，只是在入栈左节点时，顺便打印了。
/**
* 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<int> preorderTraversal(TreeNode* root) {
vector<int> result;
if (!root) {
return result;
}
stack<TreeNode *> s;
TreeNode * node = root;
while (node || !s.empty()) {
while (node) {
result.push_back(node->val);
s.push(node);
node = node->left;
}
node = s.top()->right;
s.pop();
}
return result;
}
};
- 后序遍历
PostOrder is a little different from the inorder and preoder. when we get a most left node called cur , we can not print it and should traverse the right subtree of it firstly. and when we back to the cur after traverse all the right subtree, we should print the cur. So we need a flag to represent if it is the first time to travese cur or not.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
struct ele{
TreeNode* root;
int flag;
ele(TreeNode* r, int f):root(r),flag(f){}
};
class Solution {
public:
vector<int> postorderTraversal(TreeNode* root) {
vector<int> result;
stack<ele> s;
TreeNode* cur = root;
while(cur || !s.empty()){
while(cur){
s.push(ele(cur, 0));
cur = cur->left;
}
ele e = s.top();
if(e.flag){
result.push_back(e.root->val);
s.pop();
}else{
cur = e.root->right;
s.top().flag = 1;
}
}
return result;
}
};
- 层序遍历
第一层数目为1. 当pop 出1个时， 此时也全加入了第二层的元素。所以此时的队列大小就是第二层的大小。记录下来为size。 pop出size个后再记录下第三层的大小。。。以此类推
/**
* 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) {
queue<TreeNode *> q;
vector<vector<int>> result;
if(root == NULL){
return result;
}
TreeNode* cur = root;
q.push(cur);
vector<int> tmp;
int size = 1;
while(!q.empty()){
cur = q.front();
q.pop();
size--;
tmp.push_back(cur->val);
if(cur->left != NULL){
q.push(cur->left);
}
if(cur->right != NULL){
q.push(cur->right);
}
if(size == 0){
result.push_back(tmp);
tmp.clear();
size = q.size();
}
}
return result;
}
};
103. Binary Tree Zigzag Level Order Traversal
Given binary tree [3,9,20,null,null,15,7], return [ [3], [20,9], [15,7] ]
一开始是想每层再用个栈，其实不用，按照queue的层序遍历， 记录好奇数偶数层，每层可以从后往前或从前往后插入相应size 的vector中。
vector<vector<int> > zigzagLevelOrder(TreeNode* root) {
if (root == NULL) {
return vector<vector<int> > ();
}
vector<vector<int> > result;
queue<TreeNode*> nodesQueue;
nodesQueue.push(root);
bool leftToRight = true;
while ( !nodesQueue.empty()) {
int size = nodesQueue.size();
vector<int> row(size);
for (int i = 0; i < size; i++) {
TreeNode* node = nodesQueue.front();
nodesQueue.pop();
// find position to fill node's value
int index = (leftToRight) ? i : (size - 1 - i);
row[index] = node->val;
if (node->left) {
nodesQueue.push(node->left);
}
if (node->right) {
nodesQueue.push(node->right);
}
}
// after this level
leftToRight = !leftToRight;
result.push_back(row);
}
return result;
}
116. Populating Next Right Pointers in Each Node
Given a binary tree
struct TreeLinkNode {
TreeLinkNode *left;
TreeLinkNode *right;
TreeLinkNode *next;
} Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL. 这个题的限制条件是空间要常量级别的。二叉树是个满二茶树，把每层的左边的结点连接到下一个右边 思路：遍历每个层，从最左边开始连接到最右边 ```c++ class Solution { public:
void connect(TreeLinkNode *root) {
if (root == NULL) return;
TreeLinkNode *pre = root;
TreeLinkNode *cur = NULL;
while(pre->left) {
cur = pre;
while(cur) {
cur->left->next = cur->right;
if(cur->next) cur->right->next = cur->next->left;
cur = cur->next;
}
pre = pre->left;
}
} }; ``` 思路二： 递归的方法。 ```c++ public void connect(TreeLinkNode root) {
if(root==null) return ;
link(root.left,root.right); }
//HELPER FUNCTION TO LINK TWO NODES TOGETHER public void link(TreeLinkNode left, TreeLinkNode right){
if(left==null && right==null) return ;
left.next = right;
link(left.left,left.right);
link(left.right,right.left);
link(right.left,right.right); } ```
117. Populating Next Right Pointers in Each Node II
思路：这个题是上个题的延伸，还是层序遍历，每次从左边开始，记录好下一层的最左节点。
/**
* Definition for binary tree with next pointer.
* struct TreeLinkNode {
* int val;
* TreeLinkNode *left, *right, *next;
* TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
*/
class Solution {
public:
void connect(TreeLinkNode *root) {
TreeLinkNode *now = root;
TreeLinkNode *left = NULL;
TreeLinkNode * cur = NULL;
while(now){
while(now){
if(now->left){
if(!left){ left = cur = now->left;}
else{
cur ->next = now->left;
cur = cur->next;
}
}
if(now->right){
if(!left){ left = cur = now->right;}
else{
cur ->next = now->right;
cur = cur->next;
}
}
now =now ->next;
}
now = left;
left = cur = NULL;
}
}
};
124. Binary Tree Maximum Path Sum
Given a binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.
思路： 这个题是说找到任意一条路径， 使得节点和最大。路径可以不经过root. 解法可以用递归。对每个节点，可以选择或者不选择。如果选了这个节点，再从左边和右边递归选路径相加，最后和最大max比较
/**
* 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 {
private:
int dfs(TreeNode* root, int& maxsum) {
if(!root) return 0;
int l = max(0,dfs(root->left,maxsum));
int r = max(0,dfs(root->right,maxsum));
maxsum = max(l+r+root->val, maxsum);
return root->val + max(l,r);
}
public:
int maxPathSum(TreeNode* root) {
int maxsum = INT_MIN;
dfs(root,maxsum);
return maxsum;
}
};
606. Construct String from Binary Tree
题意是这样：先序遍历树， 对每个节点用（）括起来左右子树，但是 最右的是空节点的不用用空（）表示， 而左子树为空右子树不空的时候， 要用（）表示空的左子树
Input: Binary tree: [1,2,3,null,4]
Output: “1(2()(4))(3)”
Input: Binary tree: [1,2,3,4]
Output: “1(2(4))(3)”
/**
* 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:
string tree2str(TreeNode* t) {
if(t == NULL){
return "";
}
string s = to_string(t->val);
if(t->left || t->right){
s = s + "(";
s = s + tree2str(t->left);
s = s + ")";
}
if(t->right){
s = s + "(";
s = s + tree2str(t->right);
s = s + ")";
}
return s;
}
};
107. Binary Tree Level Order Traversal II
这个题是层序遍历，而顺序是从下到上的层。 可以普通的层序遍历后再reverse. 也可以先求出 层数， 递归遍历。
/**
* 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 findMaxLen(TreeNode* root)
{
if(root==NULL) return 0;
return 1+max(findMaxLen(root->left),findMaxLen(root->right));
}
void levelOrderRec(TreeNode* root, vector<vector<int>>& vec, int level)
{
if(root==NULL) return;
vec[level].push_back(root->val);
levelOrderRec(root->left,vec,level-1);
levelOrderRec(root->right,vec,level-1);
}
vector<vector<int> > levelOrderBottom(TreeNode *root) {
vector<vector<int>> result;
if(root==NULL) return result;
int count = findMaxLen(root);
for(int i = 0; i < count; i++)
{
vector<int> temp;
result.push_back(temp);
}
levelOrderRec(root, result, count-1);
return result;
}
};
582. Kill Process
Given n processes, each process has a unique PID (process id) and its PPID (parent process id). 每个进程有一个父进程id, 可能有多个子进程id. kill一个进程 并且把他的子进程也全杀掉 给出 pid 已经相应的ppid数组, 首先可以用广搜
lass Solution {
public:
vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
unordered_map<int, vector<int>> map;
for(int i = 0; i < pid.size(); i++){
if(map.find(ppid[i]) != map.end()){
map[ppid[i]].push_back(pid[i]);
}else{
vector<int> v;
v.push_back(pid[i]);
map.insert(make_pair(ppid[i], v));
}
}
vector<int> res;
res.push_back(kill);
int start = 0;
while(1){
unordered_map<int, vector<int>>::iterator it = map.find(res[start]);
if(it != map.end()){
for(int j = 0; j < it->second.size(); j ++){
res.push_back(it->second[j]);
}
}
start ++;
if(start == res.size()){
break;
}
}
return res;
}
};
然后还有深度优先搜索的方法：
class Solution {
public:
vector<int> killProcess(vector<int>& pid, vector<int>& ppid, int kill) {
vector<int> killed;
map<int, set<int>> children;
for (int i = 0; i < pid.size(); i++) {
children[ppid[i]].insert(pid[i]);
}
killAll(kill, children, killed);
return killed;
}
private:
void killAll(int pid, map<int, set<int>>& children, vector<int>& killed) {
killed.push_back(pid);
for (int child : children[pid]) {
killAll(child, children, killed);
}
}
};
199. Binary Tree Right Side View
题目是假设站在树的右边，然后把右视图从top到底返回。其实就是层序遍历只要最右的一个元素。
思路一： 对先序遍历的修改。 主要是判断res.size()<level 这个很巧妙
class Solution {
public:
void recursion(TreeNode *root, int level, vector<int> &res)
{
if(root==NULL) return ;
if(res.size()<level) res.push_back(root->val);
recursion(root->right, level+1, res);
recursion(root->left, level+1, res);
}
vector<int> rightSideView(TreeNode *root) {
vector<int> res;
recursion(root, 1, res);
return res;
}
};
思路二： 层序遍历
/**
* 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<int> rightSideView(TreeNode* root) {
queue<TreeNode*> q;
if(root){
q.push(root);
}
vector<int> res;
int size = 1;
while(!q.empty()){
TreeNode* cur = q.front();
q.pop();
if(cur->left){
q.push(cur->left);
}
if(cur->right){
q.push(cur->right);
}
size--;
if(!size){
res.push_back(cur->val);
size = q.size();
}
}
return res;
}
};
112. Path Sum
注意这个题目 是根到叶子节点。 需要判断某个节点是不是叶子节点呐。！！
/**
* 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 hasPathSum(TreeNode* root, int sum) {
if(root == NULL){
return false;
}
return sump(root,sum, 0);
}
bool sump(TreeNode* root, int sum, int cur){
cur = cur +root->val;
if(!root->left && !root->right){
if(cur == sum){
return true;
}else{
return false;
}
}
if(root->left && sump(root->left, sum, cur)){
return true;
}
if(root->right && sump(root->right, sum, cur)){
return true;
}
return false;
}
};
113. Path Sum 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:
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<vector<int>> res;
if(root == NULL){
return res;
}
vector<int> tmp;
pathSum(root, sum, 0, res, tmp);
return res;
}
void pathSum(TreeNode* root, int sum, int cur, vector<vector<int>>& res, vector<int>& curV){
cur = cur + root->val;
curV.push_back(root->val);
if(!root->left && !root->right){
if(cur == sum){
res.push_back(curV);
}
curV.pop_back();
}else {
if(root->left){
pathSum(root->left, sum, cur, res, curV);
}
if(root->right){
pathSum(root->right, sum, cur, res,curV);
}
curV.pop_back();
}
}
};
114. Flatten Binary Tree to Linked List
题意， 就是按照先序遍历， 把树都变成只有右子树的一条线。比如 1（left:2）（right：3） 变成 1(left:null)（2((null)(3))） 思路：用 mirrors 算法。把最右的叶子的右子树指向后继节点、
/**
* 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:
void flatten(TreeNode* root) {
if(root == NULL){
return;
}
TreeNode* now = root;
while(now){
if(now->left){
TreeNode* pre = now->left;
while(pre->right){
pre = pre->right;
}
pre->right = now->right;//mirror 把最右指向后继节点
now->right = now->left;
now->left = NULL;
}
now = now->right;
}
}
};
动态规划与递归
####235. Lowest Common Ancestor of a Binary Search Tree
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (p -> val < root -> val && q -> val < root -> val)
return lowestCommonAncestor(root -> left, p, q);
if (p -> val > root -> val && q -> val > root -> val)
return lowestCommonAncestor(root -> right, p, q);
return root;
}
};
236. Lowest Common Ancestor of a Binary Tree
思路是这样： 遍历一遍，如果当前的节点等于p or q，那么返回当前的节点。否则分别查找左边和右边。如果只有一边找到了，那么返回一边的结果否则返回当前节点。
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if (!root || !p || !q) {
return NULL;
}
if (root == p || root == q) {
return root;
}
TreeNode* l = lowestCommonAncestor(root->left, p, q);
TreeNode* r = lowestCommonAncestor(root->right, p, q);
if (l && r) {
return root;
}
return l? l : r;
}
};
337 House Robber III
题意： 一颗二叉树，节点是房子，并有val值。小偷可以偷不相邻的房子，问最大偷多少val值。
思路： 动态规划的思想。对每个节点，可以偷， 偷了的话， 下面的left和right子节点都没法偷了。如果不偷， 那么下面的left，right可以偷也可以不偷。递归的话，分别记录这两种情况的最大值，向上回溯时，我们可以根据左右节点的两种情况，进行计算。
/**
* 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 rob(TreeNode* root)
{
int mt, ms;
rob(root, mt, ms);
return max(mt, ms);
}
void rob(TreeNode* node, int& mt, int& ms)
{
mt = ms = 0;
if (!node) return;
int mtl, mtr, msl, msr;
rob(node->left, mtl, msl);
rob(node->right, mtr, msr);
mt = msl + msr + node->val;
ms = max(mtl, msl) + max(mtr, msr);
return;
}
};
437
这题是要把所有片段路径为sum的个数输出
/**
* 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 {
private:
int num = 0;
public:
int pathSum(TreeNode* root, int sum) {
unordered_map<int, int> m;
m[0]++;
int total = 0;
helper(root, 0, sum, total, m);
return total;
}
void helper(TreeNode *p, int cur, int sum, int &total, unordered_map<int, int> &m) {
if (!p) return;
cur += p->val;
if (m.find(cur - sum) != m.end()) total += m[cur - sum];
m[cur]++;
helper(p->left, cur, sum, total, m);
helper(p->right, cur, sum, total, m);
m[cur]--;
}
};
222. Count Complete Tree Nodes
思路一： 直接用递归会超时，这个题目是完全二叉树，可以再递归的时候判断最左和最右的深度一样吗然后一样的话直接用公式结算节点（2^h -1） 注意每次算最左最右深度时可以记录一下避免重复计算
public class Solution {
public int countNodes(TreeNode root) {
return countNodes(root, -1, -1);
}
private int countNodes(TreeNode root, int lheight, int rheight){
// 如果没有上轮计算好的左子树深度，计算其深度
if(lheight == -1){
lheight = 0;
TreeNode curr = root;
while(curr != null){
lheight++;
curr = curr.left;
}
}
// 如果没有上轮计算好的右子树深度，计算其深度
if(rheight == -1){
rheight = 0;
TreeNode curr = root;
while(curr != null){
rheight++;
curr = curr.right;
}
}
// 如果两个深度一样，返回2^h-1
if(lheight == rheight) return (1 << lheight) - 1;
// 否则返回左子树右子树节点和加1
return 1 + countNodes(root.left, lheight - 1, -1) + countNodes(root.right, -1, rheight - 1);
}
}
另外还可以用二分等方法： http://blog.csdn.net/jmspan/article/details/51056085
96. Unique Binary Search Trees
Given n, how many structurally unique BST’s (binary search trees) that store values 1…n?
思路： 可以很容易的退出递推式，1-n,分别可以以n个节点做根，若以i做根，那么它可构成的个数为 f(i-1)*f(n-i) 相加即可 可以用递归做， 但是超时。 所以用数组存下
class Solution {
public:
int numTrees(int n) {
int ff[n + 1];
ff[0] = 1;
ff[1] = 1;
for(int i = 2; i <= n; i++){
ff[i] = 0;
for(int j = 1; j <= i; j++){
ff[i] += ff[j - 1]* ff[i - j];
}
}
return ff[n];
// return f(n);
}
// int f(int i){
// if(i == 1 || i ==0){
// return 1;
// }
// int r = 0;
// for(int j = 1; j <= i; j++){
// r += f(j-1)*f(i-j);
// }
// return r;
// }
};
95. Unique Binary Search Trees II Add to List
DescriptionHintsSubmissionsSolutions Total Accepted: 80086 Total Submissions: 257753 Difficulty: Medium Contributor: LeetCode Given an integer n, generate all structurally unique BST’s (binary search trees) that store values 1…n.
/**
* 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<TreeNode*> generateTrees(int n) {
if(n == 0){
return vector<TreeNode*>(0);
}
return help(1, n);
}
vector<TreeNode*> help(int start, int end) {
vector<TreeNode*> result;
if(start > end){
result.push_back(NULL);
return result;
}else if(start == end){
result.push_back(new TreeNode(start));
return result;
}
for(int i = start; i <= end; i++){
vector<TreeNode*> left = help(start, i - 1);
vector<TreeNode*> right = help(i+1, end);
for(int k = 0; k < left.size(); k++){
for(int j = 0; j < right.size(); j++){
TreeNode* root = new TreeNode(i); // 注意每个树都要自己new节点
root->left = left[k];
root->right = right[j];
result.push_back(root);
}
}
}
return result;
}
};
100 Same Tree
简单题， 就是判断条件的时候， 可以简写。
bool isSameTree(TreeNode* p, TreeNode* q) {
if (!p || !q) return q == p;
return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
572. Subtree of Another Tree
此题可以直接遍历 然后利用上题的same tree 判断。 另外一种思路是，这个过程特别像字符串匹配的过程，先遍历成字符串，就转换成了求是否为子串（KMP算法）问题。但我还没想明白怎么建立树的字符串，只是遍历建立的话会有样例不正确的。
/**
* 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 isSubtree(TreeNode* s, TreeNode* t) {
bool f = isEqualtree(s, t);
if(f){
return true;
}else if(s == NULL){
return false;
}
bool lf = isSubtree(s->left, t);
if(lf){
return lf;
}
bool rf = isSubtree(s->right, t);
if(rf){
return rf;
}
return false;
}
bool isEqualtree(TreeNode* s, TreeNode* t) {
if(s== NULL || t == NULL){
return s == t;
}
if(s->val != t->val){
return false;
}
return isEqualtree(s->left, t->left) && isEqualtree(s->right, t->right);
}
};
101. Symmetric Tree
Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).
For example, this binary tree [1,2,2,3,4,4,3] is symmetric: 就是判断一棵树是否对称。
- 思路1： 可以按照上题思路，最左右子树递归判断， 只是值相等的地方要左右交换
/**
* 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) {
if(root == NULL){
return true;
}
return help(root->left, root->right);
}
bool help(TreeNode *left, TreeNode * right){
if(!left || !right){
return left == right;
}
return left->val == right->val && help(left->right, right->left) && help(left->left, right->right);
}
};
- 思路2： 用两个队列，每层从左到右和从右到左入队列。
/**
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isSymmetric(TreeNode *root) {
TreeNode *left, *right;
if (!root)
return true;
queue<TreeNode*> q1, q2;
q1.push(root->left);
q2.push(root->right);
while (!q1.empty() && !q2.empty()){
left = q1.front();
q1.pop();
right = q2.front();
q2.pop();
if (NULL == left && NULL == right)
continue;
if (NULL == left || NULL == right)
return false;
if (left->val != right->val)
return false;
q1.push(left->left);
q1.push(left->right);
q2.push(right->right);
q2.push(right->left);
}
return true;
}
};
另外相似的一个题，翻转二叉树
TreeNode* invertTree(TreeNode* root) {
if(!root){
return root;
}
TreeNode* left = invertTree(root->left);
TreeNode* right = invertTree(root->right);
root->right = left;
root->left = right;
return root;
}
563. Binary Tree Tilt
Given a binary tree, return the tilt of the whole tree.
The tilt of a tree node is defined as the absolute difference between the sum of all left subtree node values and the sum of all right subtree node values. Null node has tilt 0.
The tilt of the whole tree is defined as the sum of all nodes’ tilt.
Example: Input: 1 / \ 2 3 Output: 1 Explanation: Tilt of node 2 : 0 Tilt of node 3 : 0 Tilt of node 1 : |2-3| = 1 Tilt of binary tree : 0 + 0 + 1 = 1
/**
* 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 findTilt(TreeNode* root) {
int tilt = 0;
findTilt(root, tilt);
return tilt;
}
int findTilt(TreeNode* root, int& tilt){
if(root == NULL){
return 0;
}
int lSum = 0, rSum = 0;
if(root->left){
lSum = findTilt(root->left, tilt);
}
if(root->right){
rSum = findTilt(root->right, tilt);
}
tilt += abs(lSum - rSum);
return root->val + lSum + rSum;
}
};
98 合法bst的判断
思路一： 每个节点都应该有个最大最小的限制，用递归的思路写出来
bool isValidBST(TreeNode* root) {
return isValidBST(root, NULL, NULL);
}
bool isValidBST(TreeNode* root, TreeNode* minNode, TreeNode* maxNode) {
if(!root) return true;
if(minNode && root->val <= minNode->val || maxNode && root->val >= maxNode->val)
return false;
return isValidBST(root->left, minNode, root) && isValidBST(root->right, root, maxNode);
}
思路二： 中序遍历， 如果某个节点小于前面一个了，那么非法。 当然可以用栈的形式遍历， 或者直接递归遍历
class Solution {
public:
bool isValidBST(TreeNode* root) {
TreeNode* prev = NULL;
return validate(root, prev);
}
bool validate(TreeNode* node, TreeNode* &prev) {
if (node == NULL) return true;
if (!validate(node->left, prev)) return false;
if (prev != NULL && prev->val >= node->val) return false;
prev = node;
return validate(node->right, prev);
}
};
99 Recover Binary Search Tree
恢复二叉查找树中 唯一一对颠倒的节点数据
思路: 中序遍历 ，相当于排序好的数组中有一对交换了顺序 比如： 1 2 3 4 5， 交换后1 5 3 4 2， 找到一个逆序的（5,3）， 5为交换的点之一，第二个逆序的（4,2），2为交换点。遍历可以通过递归进行， 分别设置两个节点记录颠倒的点。
/**
* 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 {
private:
TreeNode* first = NULL;
TreeNode* second = NULL;
TreeNode* prevElement = new TreeNode(INT_MIN);
public:
void recoverTree(TreeNode* root) {
t(root);
int tmp = second->val;
second->val = first->val;
first->val = tmp;
}
void t(TreeNode * root){
if(!root){
return;
}
t(root->left);
if(!first && prevElement->val > root->val){
first = prevElement;
}
if(first!=NULL && prevElement->val > root->val){
second = root;
}
prevElement = root;
t(root->right);
}
};
这道题的真正符合要求的解法应该用的Morris遍历，这是一种非递归且不使用栈，空间复杂度为O(1)的遍历方法，可参见Binary Tree Inorder Traversal 二叉树的中序遍历，在其基础上做些修改，加入first, second和parent指针，来比较当前节点值和中序遍历的前一节点值的大小，跟上面递归算法的思路相似，代码如下：
重复以下1、2直到当前节点为空
-
如果当前节点的左孩子为空，则输出当前节点并将其右孩子作为当前节点。
-
如果当前节点的左孩子不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点（即当前节点的左子树的最右节点）。
a) 如果前驱节点的右孩子为空，将它的右孩子设置为当前节点（利用这个空的右孩子指向它的后缀）。当前节点更新为当前节点的左孩子。
b) 如果前驱节点的右孩子为当前节点，将它的右孩子重新设为空（恢复树的形状）。输出当前节点。当前节点更新为当前节点的右孩子。
// Now O(1) space complexity
class Solution {
public:
void recoverTree(TreeNode *root) {
TreeNode *first = NULL, *second = NULL, *parent = NULL;
TreeNode *cur, *pre;
cur = root;
while (cur) {
if (!cur->left) {
if (parent && parent->val > cur->val) {
if (!first) first = parent;
second = cur;
}
parent = cur;
cur = cur->right;
} else {
pre = cur->left;
while (pre->right && pre->right != cur) pre = pre->right;
if (!pre->right) {
pre->right = cur;
cur = cur->left;
} else {
pre->right = NULL;
if (parent->val > cur->val) {
if (!first) first = parent;
second = cur;
}
parent = cur;
cur = cur->right;
}
}
}
if (first && second) swap(first->val, second->val);
}
};
二叉查找树
450. Delete Node in a BST
思路一：遍历找到要删除的节点， 有好几种情况：
- 该节点没有左子树（只有右子树 或 没有右子树）： 将节点的前驱节点 指向该节点的右节点；
- 该节点没有右子树，同上，将节点的前驱节点 指向该节点的左节点；
- 该节点两边都有子树。：找到右子树的最左节点，用他的值替换该节点的值。然后删除它。 前两种情况，需要我们记录下key节点的前驱节点，若key节点是root 还需要特殊处理。
/**
* 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* deleteNode(TreeNode* root, int key) {
TreeNode* del = root;
TreeNode* delPre = NULL;
while(del){
if(del->val == key){
break;
}else{
delPre = del;
if(del->val < key){
del = del->right;
}else{
del = del->left;
}
}
}
if(!del){
return root;
}
if(!del->left){
if(!delPre){
root = root->right;
return root;
}
if(delPre->val < key){
delPre->right = del->right;
}else{
delPre->left = del->right;
}
return root;
}
if(!del->right){
if(!delPre){
root = root->left;
return root;
}
if(delPre->val < key){
delPre->right = del->left;
}else{
delPre->left = del->left;
}
return root;
}
TreeNode*pre = del;
TreeNode* next = del->right;
while(next->left){
pre = next;
next = next->left;
}
del->val = next->val;
if(pre == del){
pre->right = pre->right->right;
}else{
pre->left = pre->left->right;
}
return root;
}
};
另外可以用 指针的指针 简化代码。
/class Solution {
public:
TreeNode* deleteNode(TreeNode* root, int key) {
TreeNode** now=&root;
while((*now)!=nullptr){
if(key > (*now)->val){
now=&((*now)->right);
}else if(key < (*now)->val){
now=&((*now)->left);
}else{
break;
}
}
if((*now)!=nullptr){
if((*now)->right==nullptr){
(*now)=(*now)->left;
}else if((*now)->left==nullptr ){
(*now)=(*now)->right;
}else{
TreeNode** leftMostPtr=&((*now)->right);
while((*leftMostPtr)->left!=nullptr){
leftMostPtr=&((*leftMostPtr)->left);
}
TreeNode* newNode=(*leftMostPtr);
(*leftMostPtr)=(*leftMostPtr)->right;
// newNode->left=(*now)->left;
//newNode->right=(*now)->right;
(*now)->val=newNode->val;
}
}
return root;
}
};
