posted in OJ题解 

题目：

https://oj.leetcode.com/problems/reverse-words-in-a-string/

分析：

解法一：（相比较更麻烦点）

  1. 运用栈来解题， 先把s中的一个个单词解析出来压到栈里， 然后再出栈重组成s

  2. 有一些特殊的边界需要考虑， 比如连续出现两个空格， 单词的头尾部出现空格等等， 这些情况需要特殊处理一下。

解法二：（更巧妙， 推荐）

从后向前进行循环

    处理空格部分

    如果结果res非空， 插入一个空格

    处理非空格部分

代码：

解法一：

class Solution
{
public:
	void reverseWords(string &s)
	{
		if (s.empty())
			return;

		string word;
		stack<string> stk;
		s.push_back(' ');
		for (int i = 0; i < s.size(); i++)
		{
			if (s[i] != ' ')
				word.push_back(s[i]);
			else if (i > 0 && s[i] == ' ' && s[i-1] != ' ')
			{
				stk.push(word);
				word.clear();
			}
		}

		s.clear();
		if (stk.empty())
			return;
		while (true)
		{
			s += stk.top();
			stk.pop();
			if (stk.empty())
				break;
			else
				s.push_back(' ');
		}
		return;
	}
};

解法二：

class Solution
{
public:
	void reverseWords(string &s)
	{
		string res;

		int i = s.size() - 1;
		while (true)
		{
			while (s[i] == ' ' && i >= 0) 
				i--;
			if (i < 0) break;

			if (!res.empty())
				res.push_back(' ');

			string temp;
			while (s[i] != ' ' && i >= 0) 
			{
				temp.push_back(s[i]);
				i--;
			}
			reverse(temp.begin(), temp.end());
			res += temp;
			if (i < 0) break;
		}
		s = res;
	}
};

参考：

http://blog.csdn.net/kenden23/article/details/20701069

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39138373

posted in OJ题解 

题目

https://oj.leetcode.com/problems/palindrome-partitioning/

分析

DFS来解决这个问题。

代码

class Solution
{
public:
	vector<vector<string>> partition(string s)
	{
		if (s.empty())
			return res;

		dfs(s, 0);

		return res;
	}

	void dfs(const string &s, int index)
	{
		if (index == s.size())
			res.push_back(solution);
		else
		{
			for (int i = index; i < s.size(); i++)
			{
				string substr = s.substr(index, i-index+1);
				if (isPalindrome(substr))
				{
					solution.push_back(substr);
					dfs(s, i+1);
					solution.pop_back();
				}
			}
		}
	}
		
	bool isPalindrome(const string &s)
	{
		int left = 0;
		int right = s.size() - 1;

		while (left <= right)
		{
			if (s[left] != s[right])
				return false;
			left++;
			right--;
		}
		return true;
	}

	vector<vector<string>> res;
	vector<string> solution;
};

参考

http://fisherlei.blogspot.com/2013/03/leetcode-palindrome-partitioning.html

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39064961

posted in OJ题解 

题目

https://oj.leetcode.com/problems/balanced-binary-tree/

分析

平衡树的判定是每个结点的左右子树的高度差不能超过1

解法一：

判定以某一节点为根的树是否为平衡树可以分解为两步：

  1. 判定左右子树的高度差是否不超过1

  2. 判定左右子树是否为平衡树

解法二：

可以进行一点优化， 让解法以的两个判定在一起完成， 不过两个算法都是一个数量级的。

代码

解法一：

class Solution
{
public:
	bool isBalanced(TreeNode *root)
	{
		if (!root)
			return true;

		int l = depth(root->left);
		int r = depth(root->right);

		if (l-r > -2 && l-r < 2 
				&& isBalanced(root->left)
				&& isBalanced(root->right))
			return true;
		else
			return false;
	}

	int depth(TreeNode *root)
	{
		if (!root)
			return -1;
		else
			return max(depth(root->left), depth(root->right)) + 1;
	}
};

解法二：

class Solution
{
public:
	bool isBalanced(TreeNode *root)
	{
		if (root == NULL)
			return true;
		else if (depth(root) == -2)
			return false;
		else
			return true;
	}

	int depth(TreeNode *node)
	{
		if (node == NULL)
			return -1;

		int left = depth(node->left);
		if (left == -2)
			return -2;

		int right = depth(node->right);
		if (right == -2)
			return -2;

		if (left-right>1 || left-right<-1)
			return -2;

		return max(left, right) + 1;
	}
};

参考

http://blog.csdn.net/lanxu_yy/article/details/11883083

http://fisherlei.blogspot.com/2013/01/leetcode-balanced-binary-tree-solution.html

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39028911

posted in OJ题解 

题目：

https://oj.leetcode.com/problems/binary-tree-postorder-traversal/

分析：

  1. 第一种方法，用递归的方法做

  2. 第二种方法，用迭代的方法做。 先挖个坑， 以后填上

代码：

class Solution
{
public:
	vector<int> postorderTraversal(TreeNode *root)
	{
		postorder(root);

		return res;
	}

	void postorder(TreeNode *root)
	{
		if (!root)
			return;
		postorderTraversal(root->left);
		postorderTraversal(root->right);
		res.push_back(root->val);

		return;
	}

private:
	vector<int> res;
};

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39028031

posted in OJ题解 

题目

https://oj.leetcode.com/problems/binary-tree-preorder-traversal/

分析

  1. 第一种方法采用递归版先序遍历。

  2. 第二种方法用循环和递归实现迭代版先序遍历。

代码

递归版

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)
	{
		preorder(root);

		return res;
	}
	
	void preorder(TreeNode *root)
	{
		if (!root)
			return;
			
		res.push_back(root->val);
		preorderTraversal(root->left);
		preorderTraversal(root->right);
	}
private:
	vector<int> res;
};

迭代版

class Solution
{
public:
	vector<int> preorderTraversal(TreeNode *root)
	{
		while (true)
		{
			preorder(root);
			if (stk.empty())
				break;
			root = stk.top();
			stk.pop();
		}
		return res;
	}
	void preorder(TreeNode *root)
	{
		while (root)
		{
			res.push_back(root->val);
			if (root->right)
				stk.push(root->right);
			root = root->left;
		}
	}

private:
	vector<int> res;
	stack<TreeNode *> stk;
};

参考

《数据结构》 邓俊辉

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/38942895

posted in OJ题解 

题目

https://oj.leetcode.com/problems/sum-root-to-leaf-numbers/

分析

DFS

代码

class Solution
{
public:
	int sumNumbers(TreeNode *root)
	{
		int solution = 0;

		if (!root)
			return 0;
		dfs(root, solution);

		return sum;
	}

	void dfs(TreeNode *root, int solution)
	{
		if (!root->left && !root->right)
		{
			solution = solution * 10 + root->val;
			sum += solution;
		}
		else
		{
			solution = solution * 10 + root->val;
			if (root->left)
				dfs(root->left, solution);
			if (root->right)
				dfs(root->right, solution);
		}
	}

private:
	int sum = 0;
};

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/38928263

posted in OJ题解 

题目

https://oj.leetcode.com/problems/binary-tree-level-order-traversal-ii/

分析

和Binary Tree Level Order Traversal一样， 只不过在最后把结果反转一下就行了。

代码

class Solution
{
public:
	vector<vector<int>> levelOrderBottom(TreeNode *root)
	{
		queue<TreeNode*> nodeQue;
		queue<int> depQue;
		TreeNode *node;
		int dep;
		int depBefore;
		vector<vector<int>> res;
		vector<int> solution;

		if (!root)
			return res;

		nodeQue.push(root);
		depQue.push(1);
		depBefore = 1;
		while (!nodeQue.empty())
		{
			node = nodeQue.front();
			nodeQue.pop();
			dep = depQue.front();
			depQue.pop();

			if (dep == depBefore)
				solution.push_back(node->val);
			else
			{
				res.push_back(solution);
				depBefore = dep;
				solution.clear();
				solution.push_back(node->val);
			}

			if (node->left)
			{
				nodeQue.push(node->left);
				depQue.push(dep + 1);
			}
			if (node->right)
			{
				nodeQue.push(node->right);
				depQue.push(dep + 1);
			}
		}
		res.push_back(solution);
		reverse(res.begin(), res.end());
		
		return res;
	}
};

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/38927307

/** * RECOMMENDED CONFIGURATION VARIABLES: EDIT AND UNCOMMENT THE SECTION BELOW TO INSERT DYNAMIC VALUES FROM YOUR PLATFORM OR CMS. * LEARN WHY DEFINING THESE VARIABLES IS IMPORTANT: https://disqus.com/admin/universalcode/#configuration-variables*/ /* var disqus_config = function () { this.page.url = PAGE_URL; // Replace PAGE_URL with your page's canonical URL variable this.page.identifier = PAGE_IDENTIFIER; // Replace PAGE_IDENTIFIER with your page's unique identifier variable }; */ (function() { // DON'T EDIT BELOW THIS LINE var d = document, s = d.createElement('script'); s.src = 'https://chenzz.disqus.com/embed.js'; s.setAttribute('data-timestamp', +new Date()); (d.head || d.body).appendChild(s); })();