题目链接 题意：求一棵二叉树中，所有一段连续路径之和等于给定值的路径数目。 思路：想了半天就只能想到暴力。。。复杂度大概O(n^2)。。。也不是不可以接受。。。但是感觉这也太暴力了。。就去看了题解。。。发现题解就还真是暴力orz。。。 /** * 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 { //思路：枚举每个起 …

题目链接 题意：判断一棵二叉树是否是自己的镜像。做法是做个copy，相当于两棵树做比较。注意逻辑不要漏掉就好 /** * 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 leaf(TreeNode* root) { if …

题目链接 题意：判断一颗二叉树是否平衡.... 思路：直接搞就好了。。。神TM又忘记dfs的时候忘记返回子调用的值。。。。我这是药丸啊。。。 /** * 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 leaf(TreeNode* root) …

题目链接 题意：求一个BST中某两个节点LCA.... 思路：卧槽。。。竟然求LCA...直接想到的显然是Tarjan的方法或者。。。RMQ+DFS。。。但是感觉。。。leetcode怎么可能考算法。。。。于是想到。。。可以从BST下手。。。 两个节点的LCA的值一定在这两个节点之间。 可以根据这个条件做二分。。。 这道题的收获是。。。不要被已知的东西限制住思路。。。tarjan或者RMQ+DFS显然也能做。。。但是那样的相当于没有用到BST的条件。。。 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; …

题目链接 题意：求一棵树的深度。。。。 思路：。。。定义搞即可。。按照左右子树中大的算。。。因为据说是经典题（虽然并不觉得2333。。。所以记录下。。。 /** * 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 dfs(TreeNode* root) { if (root==NULL) …

题目链接 题意：反转一棵二叉树。。。字面意思理解即可。。就是把每一棵子树的左右孩子交换。。。 思路：直接照着题意做就好了。。。没有坑。。记录的原因是听说这题比较经典（虽然毫无难度... /** * 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 leaf(TreeNode* root) { if …

题目链接 题意：给一棵树。。问是否存在一条从树根到叶子的路径，使得路径上每个点的val之和等于给定的sum。 思路：。。。直接搞就好。。。由于是比较经典的题目所以记录一下。。。注意递归的时候每一部分都要返回值orz..(我是多久没写代码了。。。 /** * 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: …

leetcode108 题意：把有一个有序的数组转化成一课高度尽量小的bst(二叉搜索树) 思路：我竟然忘记了什么是bst........我好傻啊...不过想想可能是因为...最朴素的二叉搜索树几乎用不到...所以很容易忘记吧2333 bst是 binary search tree的缩写.. 具体见 维基百科_二叉搜索树 想起来概念就好搞了...直接递归建树即可...类似线段树的build的过程 /* *********************************************** Author :111qqz Created Time :2017年02月21日 星期二 13时08分04秒 File Name …

最近要准备面试...虽然leetcode的题目难度比较水..不过白板写代码还是要练下的。。。我所理解的白板写代码。。。大概就是。。。用记事本。。一遍写对代码的能力吧。。。所以我来记录一下。。思路想错的或者没有秒的题目。 （因为题目描述傻逼/数据范围故意坑人/leetcode抽风 / 我自己犯傻逼 等原因 没有一次通过的题目不在记录之列） leetcode107 题意：给一棵二叉树，从最底层往上依次输出每一个node的val.. 思路：一开始以为同一层的一定会在相邻时间内访问。。。后来发现的确是蠢了。。。 因此dfs的时候加了一个level域。。。每次dfs的时候先左后右就好了。。。 注意记得判断root为空的情况。。。 /* …

第一次参加面试orz...所以还是有点期待+紧张的2333 题目比较多，30分钟做了一半吧，之后就是和面试官聊。 优先编程题。 由于题目不可能做完。。我基本上是跳着做的。。。 看到一道求斐波那契第n项的题。。。我随口问面试官n的数据范围。。。 他说越优越好。。我问能实现的n越大越好？他说时间空间复杂度越低越好。 因为题目显然做不完。。我又确认了下。。是尽可能多做。。还是尽可能把每道题做优。。。 面试官说是后者。。 我想了一下。。。写了个lgn的算法。。。 然后有一道求等比数列第n项的题。。。 想了一下。。。不知道怎么优化。。就写了暴力。。。用了pow函数。。 之后面试官问我pow的实现原理。。。 我说好像是。。。康托展开。。？啊 …