字典树(查找树)26个分支作用：检测字符串是否在这个字典里面插入、查找字典树与哈希表的对比：时间复杂度：以字符来看：O(N)、O(N)以字符串来看：O(1)、O(1)空间复杂度：字典树远远小于哈希表前缀相关的题目字典树优于哈希表字典树可以查询abc是否有ab的前缀字典树常考点：1.字典树实现2.利用字典树前缀特性解题3...

108.ConvertSortedArraytoBinarySearchTree这个题使用二分查找，主要要注意边界条件。如果left>right，就返回NULL。每次更新的时候是mid-1，mid+1。自己推一下基本就可以验证了。classSolution{public:TreeNode*sortedArrayT...

 https://www.cnblogs.com/grandyang/p/9914546.html 类似于二分查找的方法，用迭代的方法去做注意：无论是进入左子树还是右子树，左右子树都变成了新的数，所以需要重新根据root->left=....来重新生成classSolution{public:...

完全二叉树的定义：若设二叉树的深度为h，除第h层外，其它各层(1～h-1)的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树。解题思路：将树按照层进行遍历，如果出现null后还出现非null则能证明这个不是完全二叉树https://leetcode.com/problems/check-com...

 classSolution{public:boolisBalanced(TreeNode*root){intdepth=0;returnBalanced(root,depth);}boolBalanced(TreeNode*root,int&depth){if(root==NULL){depth=0...

104:classSolution{public:intmaxDepth(TreeNode*root){if(root==NULL)return0;intleft=maxDepth(root->left);intright=maxDepth(root->right);return(left>right...

124.BinaryTreeMaximumPathSumhttps://www.cnblogs.com/grandyang/p/4280120.html如果你要计算加上当前节点的最大path和，这个节点的左右子树必定是纯左右树(即没有拐点)，用另一个参数保留整个二叉树的最大path和，然后计算每一个以当前节点为拐点的路...

207.CourseSchedulehttps://blog.csdn.net/wongleetion/article/details/79433101问题的实质就是判断一个有向图是否有环，利用入度去解决这个问题使用bfs解决问题。初始化时，利用二维vector存储节点间的关系，并存储每个节点的入度，同时将入度为0的节...

  https://www.cnblogs.com/grandyang/p/4297300.html用堆来辅助，先存储所有的左节点，再根据左节点找右节点classSolution{public:vector<int>inorderTraversal(TreeNode*root){vect...

https://www.cnblogs.com/grandyang/p/4641968.htmlhttp://www.cnblogs.com/grandyang/p/4640572.html利用二叉搜索树的性质：左子树所有节点小于根节点，右子树所有节点大于根节点如果两个节点的最大值小于根节点，那最低公共祖先一定在左子树...

错误解法classSolution{public:boolisValidBST(TreeNode*root){if(root==NULL)returntrue;boolleft=isValidBST(root->left);boolright=isValidBST(root->right);if(left=...

96.UniqueBinarySearchTreeshttps://www.cnblogs.com/grandyang/p/4299608.html3由dp[1]*dp[1]、dp[0]*dp[2]、dp[2]*dp[0]相加而成从2开始classSolution{public:intnumTrees(intn){ve...

 https://www.cnblogs.com/grandyang/p/7058935.htmlclassSolution{public:TreeNode*mergeTrees(TreeNode*t1,TreeNode*t2){if(!t1)returnt2;if(!t2)returnt1;TreeNode...

https://www.cnblogs.com/grandyang/p/6591526.html这个题本质上是中序遍历的反向。中序遍历是从小到大，而这个题目是从大到小，然后每个数加上比自己大的所有数的和。因为实际上并没有改变树的结构，只是改变了原来树中节点的值，所以用void做返回值就可以了。每次加sum实际上就是加的...

和剑指上树的子结构的题稍稍有点不同，3/45/12/04/12这两个在这个题目中不是子树的关系，但剑指那个题这种情况算是子树classSolution{public:boolisSubtree(TreeNode*s,TreeNode*t){boolresult=false;if(s!=NULL&&t!=...