KK's blog

LeetCode 112 Path Sum

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

              
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

题目大意：

给定一个二叉树root和一个和sum，决定这个树是否存在一条从根到叶子的路径使得沿路所有节点的和等于给定的sum。

解题思路：

DFS搜索，二叉树的题。步骤主要是考虑

1. 空指针
2. 一个node情况或多个node情况（可合并）

注意事项：

1. 叶子节点是不含左儿子和右儿子

Java代码：

1
2
3
4
5
6
7

public boolean hasPathSum(TreeNode root, int sum) {
	if(root == null)
		return false;
	if(root.left==null && root.right==null && root.val==sum)
		return true;
	return hasPathSum(root.left, sum-root.val) || hasPathSum(root.right, sum-root.val);        
}

算法分析：

两种方法时间复杂度为O(n)，n为节点数。空间复杂度为O(h)，h为二叉树高度。

相关题目：

LeetCode 112 Path Sum
LeetCode 124 Binary Tree Maximum Path Sum

LeetCode 557 Reverse Words in a String III

Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.

Example 1:

Input: "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"

Note:In the string, each word is separated by single space and there will not be any extra space in the string.

题目大意：

给定字符串，将每个单词逐字符逆置，返回新字符串。注意：字符串中单词之间有且只有1个空格分开。

解题思路：

这里考到StringBuilder，对于字符串连接效率高。还有一个小技巧，就是往输入参数附加一个空格，这样for循环结束后不用特别处理边界情况。
第一种方法是以单词为扫描单位，把字符串分成单词字符串数组，然后把每个单词反转及一个空格加入到结果sb中。
第二种方法是以字符为扫描单位，遇到空格是，就把之前存入的word放入sb中，再进行下一轮word扫描。

注意事项：

1. 用StringBuilder
2. 末尾加入空格

Java代码：

第一种方法

1
2
3
4
5
6
7
8

public String reverseWords(String s) {
	String[] tokens = s.split(" ");
	StringBuilder sb = new StringBuilder();
	for(String token : tokens)
		sb.append(new StringBuilder(token).reverse().toString()+" ");
	
	return sb.toString().trim();
}

第二种方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

public String reverseWords(String s) {
	s = s+" ";
	StringBuilder sb = new StringBuilder();
	StringBuilder word = new StringBuilder();
	for(char c : s.toCharArray()){
		if(c!=' ')
			word.append(c);
		else
		{
			sb.append(word.reverse().toString()+" ");
			word = new StringBuilder();
		}
	}
	return sb.toString().trim();
}

算法分析：

两种方法时间复杂度为O(n)，n为字符串长度。第一种方法空间复杂度为O(n)，而第二种方法为O(1)。

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1

$ hexo new "My New Post"

More info: Writing

Run server

1

$ hexo server

More info: Server

Generate static files

1

$ hexo generate

More info: Generating

Deploy to remote sites

1

$ hexo deploy

More info: Deployment