只记录做了的题目和感觉有收获的题目
今日完成：
18.重建二叉树
好久没做这种基础题了，感觉都不会了……果然基础很重要。
/**
* 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:
unordered_map<int,int> pos;
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int len=preorder.size();
for(int i=0;i<len;i++)
pos[inorder[i]]=i;//方便根据先序遍历中的根节点位置在中序遍历中找到相应位置
return dfs(preorder,inorder,0,len-1,0,len-1);
}
TreeNode* dfs(vector<int>& preorder, vector<int>& inorder,int pl,int pr,int il,int ir){
if(pl>pr||il>ir) return NULL;
if(pl<0||il<0) return NULL;
int k=pos[preorder[pl]]-il;//计算出左子树的节点个数
TreeNode* root=new TreeNode(preorder[pl]);//以当前根节点为对象建立一棵树
root->left=dfs(preorder,inorder,pl+1,pl+k,il,il+k-1);
root->right=dfs(preorder,inorder,pl+k+1,pr,il+k+1,ir);
return root;
}
};
模板题目，记忆方法。如果看不懂就建树模拟
19.二叉树的下一个节点
主要思路：中序遍历是左根右，那么如果待求节点有右孩子，则待求节点中序遍历的下一个节点应当是其右孩子的最左节点。如果没有，那么待求节点中序遍历的下一个节点应当是向上的某个p节点，该节点是第一个是其father左孩子的节点。不懂就画图尝试。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode *father;
* TreeNode(int x) : val(x), left(NULL), right(NULL), father(NULL) {}
* };
*/
class Solution {
public:
TreeNode* inorderSuccessor(TreeNode* p) {
//中：左、根、右
if(p->right){
p=p->right;
while(p->left)
p=p->left;
return p;
}
while(p->father&&p==p->father->right) p=p->father;
return p->father;
}
};
心得
注意基础题目的熟练掌握，注意库函数的记忆！