↓ 跳过正文
111qqz的小窝
111qqz的小窝
  1. Posts/

leetcode 437. Path Sum III

·242 字·1 分钟
ACM Brute Force Leetcode

题目链接

题意：求一棵二叉树中，所有一段连续路径之和等于给定值的路径数目。

思路：想了半天就只能想到暴力。。。复杂度大概O(n^2)。。。也不是不可以接受。。。但是感觉这也太暴力了。。就去看了题解。。。发现题解就还真是暴力orz。。。

 1/**
 2 * Definition for a binary tree node.
 3 * struct TreeNode {
 4 *     int val;
 5 *     TreeNode *left;
 6 *     TreeNode *right;
 7 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8 * };
 9 */
10class Solution {  //思路：枚举每个起点？？？好暴力啊。。。卧槽。。正解就是这样。。。
11public:
12	 int dfs(TreeNode* root,int sum)
13	{
14		int res = 0 ;
15		if (root==NULL) return res;
16		if (root->val==sum) res++;
17		res += dfs(root->left,sum-root->val)+dfs(root->right,sum-root->val);
18		return res;
19	}
20    int pathSum(TreeNode* root, int sum) {
21		if (root==NULL) return 0;
22		return dfs(root,sum)+pathSum(root->left,sum)+pathSum(root->right,sum);
23    }
24};

相关文章

leetcode 101. Symmetric Tree Add to List（二叉树，判断镜像）

·247 字·1 分钟
ACM Leetcode
题目链接 题意：判断一棵二叉树是否是自己的镜像。做法是做个copy，相当于两棵树做比较。注意逻辑不要漏掉就好 1/** 2 * Definition for a binary tree node. 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */ 10class Solution { 11public: 12 13 bool leaf(TreeNode* root) 14 { 15 if (root->left==NULL&&root->right==NULL) return true; 16 return false; 17 } 18 bool mirror(TreeNode* rt1,TreeNode* rt2) 19 { 20 21 if (rt1==NULL&&rt2==NULL) return true; 22 if (rt1==NULL||rt2==NULL) return false; 23 printf("%d %d\n",rt1->val,rt2->val); 24 if (leaf(rt1)&&leaf(rt2)&&rt1->val==rt2->val) return true; 25 if (leaf(rt1)||leaf(rt2)) return false; //包含了其中一个是叶子，或者两个都是叶子但是值不相等的情况。 26 if (rt1->val!=rt2->val) return false; //不是叶子，但是值不相等，没必要继续了。 27 bool res = true; 28 res = mirror(rt1->left,rt2->right); 29 if (!res) return false; 30 res = mirror(rt2->left,rt1->right); 31 if (!res) return false; 32 return true; 33 } 34 bool isSymmetric(TreeNode* root) { 35 if (root==NULL) return true; 36 return mirror(root,root); 37 38 } 39};

leetcode 110. Balanced Binary Tree

·238 字·1 分钟
ACM Leetcode
题目链接 题意：判断一颗二叉树是否平衡…. 思路：直接搞就好了。。。神TM又忘记dfs的时候忘记返回子调用的值。。。。我这是药丸啊。。。 1 /** 2 * Definition for a binary tree node. 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */ 10class Solution { //错误原因：左右子树都平衡的树未必平衡！！！！ 11public: 12 bool leaf(TreeNode* root) 13 { 14 if (root->left==NULL&&root->right==NULL) return true; 15 return false; 16 } 17 int dep(TreeNode* root) 18 { 19 if (root==NULL) return 0; 20 return max(dep(root->left),dep(root->right))+1; 21 } 22 bool dfs(TreeNode* root) 23 { 24 bool res = true; 25 if (abs(dep(root->left)-dep(root->right))>1) return false; 26 if (root->left!=NULL) res = dfs(root->left); 27 if (!res) return false; 28 if (root->right!=NULL) res = dfs(root->right); 29 if (!res) return false; 30 return true; 31 } 32 bool isBalanced(TreeNode* root) { 33 if (root==NULL) return true; 34 bool res = dfs(root); 35 return res; 36 } 37};

leetcode 104. Maximum Depth of Binary Tree（求一棵树的深度）

·158 字·1 分钟
ACM Leetcode
题目链接 题意：求一棵树的深度。。。。 思路：。。。定义搞即可。。按照左右子树中大的算。。。因为据说是经典题（虽然并不觉得2333。。。所以记录下。。。 1/** 2 * Definition for a binary tree node. 3 * struct TreeNode { 4 * int val; 5 * TreeNode *left; 6 * TreeNode *right; 7 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8 * }; 9 */ 10class Solution { 11public: 12 13 int dfs(TreeNode* root) 14 { 15 if (root==NULL) return 0; 16 return max(dfs(root->left),dfs(root->right))+1; 17 } 18 19 int maxDepth(TreeNode* root){ 20 if (root==NULL) return 0; 21 int res = dfs(root); 22 return res; 23 24 25 } 26};

leetcode 226. Invert Binary Tree（反转二叉树）

·208 字·1 分钟
ACM Leetcode
题目链接 题意：反转一棵二叉树。。。字面意思理解即可。。就是把每一棵子树的左右孩子交换。。。 思路：直接照着题意做就好了。。。没有坑。。记录的原因是听说这题比较经典（虽然毫无难度…