KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

算法思路：

图用邻接表为输入，思路递归实现, 还要一个机制记录节点访问过没有，可以用HashSet，同时它作为结果存储BFS访问结果。
BFS多用于找最短路径
DFS多用于快速发现底部节点和具体路劲问题（如路径和或打印路径）。

BFS优缺点：
同一层的所有节点都会加入队列，所以耗用大量空间
仅能非递归实现
相比DFS较快，空间换时间
适合广度大的图

DFS优缺点：
无论是系统栈还是用户栈保存的节点数都只是树的深度，所以空间耗用小
有递归和非递归实现
由于有大量栈操作（特别是递归实现时候的系统调用），执行速度较BFS慢
适合深度大的图

如果BFS和DFS都可以用，建议用BFS，因为工业应用中，BFS不用有限的栈空间，可以利用到所有内存。

图DFS

算法步骤：

  1. 不合法情况（已访问、越界、trivial情况等）返回。
  2. 标记为已访问。
  3. 递归访问相邻节点。
  4. DFS路径尽量记录在数组中而非ArrayList中，路径(图)再DFS后要恢复为原状态L332。

Python代码：

1
2
3
4
5
6
7
def dfs(self, graph, start, visited, res):
	if start in visited:
		return
	visited.add(start)
	res.append(start)
	for node in graph[start]:
		self.dfs(graph, visited, node, res)

字符型DFS

注意事项：

  1. 输入值为空的情况或空节点
  2. 求得解以后复制path到result中
  3. 终止条件记得return
  4. 每次递归完恢复输入图或中间结果path的状态，递归式用i + 1

Python代码：

1
2
3
4
5
6
def dfs(self, input, start, endIndex, path, result): 
    if start == endIndex: 
        result.append(list(path))
        return 
    for i in <func>(input[start]): 
        self.dfs(input, i + 1, endIndex , path + input[i], result)

填位法

类似于排列(visited)，组合模板(带start)，组合模板是的下一轮递归用i + 1, 但这里由于是填位，一位一位加入，所以是start + 1

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
def dfs(self, n, start, path, res, col_set):
	if start == n: # remember not len(path)
		res.append(list(path))
		return
	for i in range(n): 
		if not self.is_valid(start, i, col_set):
			continue
		path.append(i) 
		col_set.add(i)
		self.dfs(n, start + 1, path, res, col_set)
		col_set.remove(i)
		path.pop()

Catalan法(双边递归)

DFS中几乎是最难的类型。考得很少。主要思想是左右儿子递归结果叉乘，再将所有结果返回。所以返回值一定是list

注意事项：

  1. 返回结果是解的集合，所以终止条件返回也需要是一个list
  2. 循环中除掉自己，递归左部分和右半部分，叉乘它们的结果
  3. 与记忆性搜索的模板类似，有时需要和它一起用，见LeetCode 241 Different Ways to Add Parentheses

Python代码：

1
2
3
4
5
6
7
8
9
def dfs(self, input):
	if <终止条件>:
		return [] # remember to use list
	res = []
    for i in range(len(input)):
        left_res = self.dfs(input[:i])
        right_res = self.dfs(input[i + 1:])
        res += [<calculate results> for _l in left_res for _r in right_res]
	return res

时间复杂度Catalan数为O(C[n] += C[i-1]*C[n-i])，空间复杂度O(1)

应用题型：

LeetCode 095 Unique Binary Search Trees II
LeetCode 241 Different Ways to Add Parentheses

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
 * graph: 邻接表
 * visited: 记录已访问节点，避免重复访问
 * start: DFS的根节点
 */
public void dfs(HashMap<Integer, LinkedList<Integer>> graph, HashSet<Integer> visited, int start){
	if(visited.contains(start)){
		return;
	}
	visited.add(start);
	System.out.print(start+",");
	for(Integer child : graph.get(start)){
		dfs(graph, visited, child);
	}
}

算法分析：

时间复杂度为O(n)，h为树的高度，空间复杂度O(h)，如果用系统栈，可理解其为O(1)。

Posted on Edited on Disqus:

LeetCode 123 Best Time to Buy and Sell Stock III

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

题目大意：

假设你有一个数组，它的第i个元素是一支给定的股票在第i天的价格。设计一个算法来找到最大的利润。你最多可以完成两笔交易。

解题思路：

回顾一下前两题：只能进行一次交易和可以无数次交易。分别是用(min, p),sum(prices[i]-prices[i-1])的方法。这题很明显比较接近只能进行一次交易的题。
如果考虑将此问题分为两个子问题(Divide & Conquer,二分法)，prices[0,k]和prices[k,n-1]，只要将k取遍所有值就得到解。

Java代码：

1
2
3
4
5
6
7
8
9
10
public int maxProfit(int[] prices) {
	int max = 0;
	for(int i=0;i<prices.length;i++){
		int p = maxProfitSingle(Arrays.copyOfRange(prices,0, i+1))
				+ maxProfitSingle(Arrays.copyOfRange(prices,i, prices.length));
		if(max<p)
			max = p;
	}
	return max;
}

算法分析：

时间复杂度为O(n2)，空间复杂度O(1)。

上述解法并非最优，因为计算prices[0,k-1]到prices[0,k]时候再次重复计算用了O(n)，但由只能进行一次交易题解中知道，其实O(1)可得，只要在计算过程中把结果存入left数组中即可。
下面的难点在于计算prices[k,n-1]。右端点固定，从右到左计算，所以其实是只能进行一次交易题解的逆运算并把结果存入到right数组。区别是(max, p)。最后只要遍历left[k]+right[k],即可得到最大利润。

注意事项：

  1. 数组长度为0。
  2. 二分法
  3. 用数组存储重复计算结果(DP)

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public int maxProfit(int[] prices) {
	if(prices.length==0)
		return 0;
	//前i天最大利润，并非需要第i天卖出
	int[] left = new int[prices.length];
	int[] right = new int[prices.length];
	
	int min = prices[0], maxPL = 0;
	for(int i=0;i<prices.length;i++){
		int p = prices[i] - min;
		if(maxPL<p)
			maxPL = p;
		left[i] = maxPL;
		if(min>prices[i])
			min=prices[i];
	}
	int max=prices[prices.length-1],maxPR=0;
	for(int j=prices.length-1;j>=0;j--){
		int p=max-prices[j];
		if(maxPR<p)
			maxPR = p;
		right[j] = maxPR;
		if(max<prices[j])
			max=prices[j];
	}
	int maxP = 0;
	for(int k=0;k<prices.length;k++){
		if(maxP<left[k]+right[k])
			maxP = left[k]+right[k];
	}
	return maxP;
}

算法分析：

时间复杂度为O(n)，空间复杂度O(n)。

相关题目：

LeetCode 121 Best Time to Buy and Sell Stock
LeetCode 122 Best Time to Buy and Sell Stock II
LeetCode 309 Best Time to Buy and Sell Stock with Cooldown
LeetCode 123 Best Time to Buy and Sell Stock III

Posted on Edited on Disqus:

算法思路：

DFS用于需要知道具体路径的问题，而并查集方法用于不需知道具体路径只关心连通性的问题。
此算法把同一个连通集归结为同一个根节点，作为判断是否一个连通集的标识。它用深度为2的扁平树组织起来。这是查找操作。
另一个关键操作是联合两个不同连通集，就是直接把根节点直接作为另一课树的子节点。在这个过程中，新的树深度可能会大于2，但当要union路径大于2的节点是，会对其进行路径压缩。
最巧妙的操作当属find操作，将路径进行压缩，变成长度为1的路径，见步骤4。
可能有人会考虑用HashMap而不是树，HashMap查找也是很高效，但联合操作比较费时，因为要更新另一个树的所有节点的根节点。

算法步骤：

  1. 初始化UnionFind类，包括3个属性：count（独立连通数）, parent（某节点的父节点）, rank（连通集排名，只有每个连通集根节点的rank不为0，其他点均为0。这是一个描述连通集规模的变量，如果规模越大，
    rank值可能越大。合并时候，rank较小的话，规模也较小，这样用rank小的合并到rank大的，需要压缩路径的节点较少，复杂度更低）。合格的节点的parent初始化为自己的id，rank为0，count为所有合格节点数量。
  2. 遍历所有节点，union此节点及其相邻的节点（如上下左右）
  3. union时候，先find两节点的根节点，若相同忽略。若不同，合并此两连通集：rank大的连通集，作为rank小的连通集的父节点。若rank相等，选任一作为另一个的父节点且把它的rank加1。count减1。
    如下图，union 5和1的，find(6)会进行压缩路径，把6接到5下。
  4. find寻找根节点的同时，压缩成与根节点路径为1的连通。

例子矩阵：
{‘0’,’1’,’1’,’0’,’0’}
{‘1’,’1’,’1’,’0’,’0’}

应用条件：

动态计算连通数如305. Number of Islands II

注意事项：

  1. find中是if语句不是while语句，因为递归已经达到
  2. union中，是祖先节点相连，不是输入相连
  3. union的调用在类外面调用，不是在init里做

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class UnionFind:

    def __init__(self, li):
        self.parent = collections.defaultdict(str)
        for s in li:
			self.parent[s] = s

    def find(self, s):
        if self.parent[s] != s:  # if statement
            self.parent[s] = self.find(self.parent[s])
        return self.parent[s]

    def union(self, s1, s2):
        root, root2 = self.find(s1), self.find(s2)
        if root != root2:
            self.parent[root] = root2 # remember not self.parent[s] = s2

注意事项：

find要注意压缩路径parent[i] = find(parent[i])

初始化：

1
2
3
4
5
6
7
8
9
10
class UnionFind {
	int[] parent;
	
	public Initialization(int n) {
        // initialize your data structure here.
        parent = new int[n + 1];
        for (int i = 1; i <= n; ++i)
            father[i] = i;
    }
}

查找：

1
2
3
4
5
6
public int find(int i) {
	if (parent[i] != i) {
		parent[i] = find(parent[i]); // path compression
	}
	return parent[i];
}

合并：

1
2
3
4
5
6
public void union(int a, int b) {
	int root_a = find(a);
	int root_b = find(b);
	if (root_a != root_b)
		parent[root_a] = root_b;
}

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
class UnionFind {
	int count; // # of connected components
	int[] parent;
	int[] rank;

	public UnionFind(char[][] grid) { // for problem 200
		count = 0;
		int m = grid.length;
		int n = grid[0].length;
		parent = new int[m * n];
		rank = new int[m * n];
		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < n; ++j) {
				if (grid[i][j] == '1') {
					parent[i * n + j] = i * n + j;
					++count;
				}
				rank[i * n + j] = 0;
			}
		}
	}

	public int find(int i) {
		if (parent[i] != i) {
			parent[i] = find(parent[i]); // path compression
		}
		return parent[i];
	}

	// union point x and y with rank
	public void union(int x, int y) {
		int rootx = find(x);
		int rooty = find(y);
		if (rootx != rooty) {
			if (rank[rootx] > rank[rooty]) {
				parent[rooty] = rootx;
			} else if (rank[rootx] < rank[rooty]) {
				parent[rootx] = rooty;
			} else {
				parent[rooty] = rootx;
				rank[rootx] += 1;
			}
			--count;
		}
	}

	public int getCount() {
		return count;
	}
}

public int numIslands3(char[][] grid) {
	if (grid == null || grid.length == 0) {
		return 0;
	}

	int nr = grid.length;
	int nc = grid[0].length;
	int num_islands = 0;
	UnionFind uf = new UnionFind(grid);
	for (int r = 0; r < nr; ++r) {
		for (int c = 0; c < nc; ++c) {
			if (grid[r][c] == '1') {
				grid[r][c] = '0';
				if (r - 1 >= 0 && grid[r - 1][c] == '1') {
					uf.union(r * nc + c, (r - 1) * nc + c);
				}
				if (r + 1 < nr && grid[r + 1][c] == '1') {
					uf.union(r * nc + c, (r + 1) * nc + c);
				}
				if (c - 1 >= 0 && grid[r][c - 1] == '1') {
					uf.union(r * nc + c, r * nc + c - 1);
				}
				if (c + 1 < nc && grid[r][c + 1] == '1') {
					uf.union(r * nc + c, r * nc + c + 1);
				}
			}
		}
	}

	return uf.getCount();
}

算法分析：

时间复杂度为O(MN)，空间复杂度O(MN)。M,N分别为矩阵长宽。遍历每个节点，而每个节点只会遍历4个相邻节点。

Ref：

并查集(Union-Find)算法介绍

Posted on Edited on Disqus:

LeetCode 200 Number of Islands

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

11110
11010
11000
00000

Answer: 1

Example 2:

11000
11000
00100
00011

Answer: 3

题目大意：

给定一个由字符‘1’（陆地）和‘0’（水域）组成的二维网格地图，计算岛屿的个数。岛屿被水域环绕，由竖直或者水平方向邻接的陆地构成。你可以假设网格地图的四条边都被水域包围。

BFS解题思路：

BFS入列后立即标记为已访问，否则会有空间和时间问题。
二维变成一维，不但节省空间，还可以避免创建Point的新class。a = x * C + y(C为列数) <=> x = a/C, y = a%C

注意事项：

  1. 注意到题目给定输入数组的类型，用其来标记已访问的单元（节点）。
  2. BFS中如果cell为0或X就要跳过，不要漏掉0，因为如果是海不应做BFS。根据题目要求，可能还要将X恢复为1.

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
OFFSETS = [(1, 0), (-1, 0), (0, 1), (0, -1)]
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    self.bfs(grid, i, j)
                    count += 1
        return count

    def bfs(self, nums, i, j):
        queue = deque([(i, j)])
        nums[i][j] = 'X'
        while queue:
            island = queue.popleft()
            for dx, dy in OFFSETS:
                x, y = island[0] + dx, island[1] + dy
                if x < 0 or x >= len(nums) or y < 0 or y >= len(nums[0]) or nums[x][y] in ['0', 'X']:
                    continue
                queue.append((x, y))
                nums[x][y] = 'X'

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public int numIslands2(char[][] grid) {
	if (grid ==null || grid.length == 0 || grid[0].length == 0)
		return 0;
	
	boolean[][] visited = new boolean[grid.length][grid[0].length];
	int islands = 0;
	for(int i = 0; i < grid.length; i++)
		for(int j=0; j < grid[0].length; j++) {
			if(grid[i][j] == '0' || visited[i][j])
				continue;
	
			bfs3(grid, i, j, visited);
			islands++;
		}
	return islands;
}

public void bfs3(char[][] grid, int a, int b, boolean[][] visited) {
	Queue<Point> q = new LinkedList<>();
	int[][] directions = new int[][] {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
	q.offer(new Point(a, b));
	visited[a][b] = true;
	while(!q.isEmpty()) {
		Point point = q.poll();
		for(int i = 0; i < 4; i++) {
			Point neighbor = new Point(point.x + directions[i][0], point.y + directions[i][1]);
			if(!isValid(grid, neighbor.x, neighbor.y) || visited[neighbor.x][neighbor.y])
				continue;
			
			q.offer(neighbor);
			visited[neighbor.x][neighbor.y] = true;
		}
	}
}

算法分析：

时间复杂度为O(MN)，空间复杂度O(min{M,N})。M,N分别为矩阵长宽。因为最坏情况下，以矩形中心为root，最大的一层为矩形里面的最大正方形，它的长度为min{M,N}。

DFS解题思路：

遍历矩阵的每一个元素，对每个元素进行DFS四个方位搜索陆地，访问过的元素在原数组中进行标记。每次DFS搜索后，层数加1。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public int numIslands(char[][] grid) {
	int layer = 0;
	for(int i=0; i<grid.length;i++)
		for(int j=0;j<grid[0].length;j++)
			if(grid[i][j]=='1'){
				dfs(grid,i,j);
				layer++;
		}
	
	return layer;
}

public void dfs(char[][] grid, int a, int b){
	if(!isValid(grid,a,b))
		return;
	
	grid[a][b] = 'x';
	dfs(grid, a+1, b);
	dfs(grid, a-1, b);
	dfs(grid, a, b+1);
	dfs(grid, a, b-1);
}

public boolean isValid(char[][] grid, int x, int y){
	if(x<0||x>=grid.length||y<0||y>=grid[0].length||grid[x][y]!='1')
		return false;
	return true;
}

算法分析：

时间复杂度为O(MN)，空间复杂度O(MN)。M,N分别为矩阵长宽。最坏情况，全为陆地，DFS退化成线性。

Union Find解题思路：

见Union Find算法详解。

  1. 初始化UnionFind类，包括3个属性：count（独立连通数）, parent（某节点的父节点）, rank（连通集排名）。合格的节点的parent初始化为自己的id，rank为0，count为所有合格节点数量。
  2. 遍历所有节点，union此节点及其相邻的节点（如上下左右）
  3. union时候，先find两节点的根节点，若相同忽略。若不同，合并此两连通集：rank大的连通集，作为rank小的连通集的父节点。若rank相等，选任一作为另一个的父节点且把它的rank加1。count减1。
    如下图，union 6和11的，find(6)会进行压缩路径，把6接到5下。
  4. find寻找根节点的同时，压缩成与根节点路径为1的连通。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
class UnionFind {
	int count; // # of connected components
	int[] parent;
	int[] rank;

	public UnionFind(char[][] grid) { // for problem 200
		count = 0;
		int m = grid.length;
		int n = grid[0].length;
		parent = new int[m * n];
		rank = new int[m * n];
		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < n; ++j) {
				if (grid[i][j] == '1') {
					parent[i * n + j] = i * n + j;
					++count;
				}
				rank[i * n + j] = 0;
			}
		}
	}

	public int find(int i) {
		if (parent[i] != i) {
			parent[i] = find(parent[i]); // path compression
		}
		return parent[i];
	}

	// union with rank
	public void union(int x, int y) {
		int rootx = find(x);
		int rooty = find(y);
		if (rootx != rooty) {
			if (rank[rootx] > rank[rooty]) {
				parent[rooty] = rootx;
			} else if (rank[rootx] < rank[rooty]) {
				parent[rootx] = rooty;
			} else {
				parent[rooty] = rootx;
				rank[rootx] += 1;
			}
			--count;
		}
	}

	public int getCount() {
		return count;
	}
}

public int numIslands3(char[][] grid) {
	if (grid == null || grid.length == 0) {
		return 0;
	}

	int nr = grid.length;
	int nc = grid[0].length;
	int num_islands = 0;
	UnionFind uf = new UnionFind(grid);
	for (int r = 0; r < nr; ++r) {
		for (int c = 0; c < nc; ++c) {
			if (grid[r][c] == '1') {
				grid[r][c] = '0';
				if (r - 1 >= 0 && grid[r - 1][c] == '1') { 
					uf.union(r * nc + c, (r - 1) * nc + c);
				}
				if (r + 1 < nr && grid[r + 1][c] == '1') {
					uf.union(r * nc + c, (r + 1) * nc + c);
				}
				if (c - 1 >= 0 && grid[r][c - 1] == '1') {
					uf.union(r * nc + c, r * nc + c - 1);
				}
				if (c + 1 < nc && grid[r][c + 1] == '1') {
					uf.union(r * nc + c, r * nc + c + 1);
				}
			}
		}
	}

	return uf.getCount();
}

算法分析：

时间复杂度为O(MN)，空间复杂度O(MN)。M,N分别为矩阵长宽。遍历每个节点，而每个节点只会遍历4个相邻节点。

Follow-up:

  1. 打印所有island坐标
  2. 计算湖的数量。湖是被island维住的水域，与海有区别。解法是先从四条边界的海域进行DFS，标记为-1，然后采用上述算法，只要将搜寻1改为搜寻0即可。
  3. 如果内存有限，不能一次读整个矩阵。方案是分块做，然后保留边界信息作为下一块的输入。
  4. 地图中途被改动。分情况，若0->1，若此单元邻居只有一种label（即使多个邻居），岛屿数不变。无邻居，岛屿数+1。邻居有多种label为n，岛屿数减少n-1。Union Find也是一个更简洁方案。
    此情况比较简单，只要查看邻居即可，因为它只会增加连接。
    若1->0, 对此单元相邻的四个单元进行DFS重新label新数，新数的种数-四单元的DSF岛屿个数=岛屿增加的个数。
    此情况需要重新做DFS，因为它破坏连接，可能导致连通性变小。

Posted on Edited on Disqus:

LeetCode 124 Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

For example:
Given the below binary tree,

       
       1
      / \
     2   3

Return 6.

题目大意：

给定一棵二叉树，寻找最大路径和。路径指的是从任意起始节点出发沿着父亲-孩子链接到达某个终止节点的节点序列。路径不一定要穿过根节点。

DFS解题思路(推荐)：

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

  1. 空指针
  2. 一个node情况或多个node情况（可合并）
    多个node情况下（比如3个节点），有4种情况下含根节点的和：左子树+根节点，右子树+跟节点，根节点，左子树+根节点+右子树。这些情况包含了所有可能的和的情况。但值得注意的是，前三种
    情况可以是子问题的解，也就是它返回值将成为此根节点父亲的左或右子树的解，但第四种情况例外，因为此情况形成的路径与根节点父亲并不在一条路径上。所以此情况应在全局变量中比较
    并不能作为返回值。
    gmax = max {return max{val,left+val,right+val} or left+val+right}

注意事项：

  1. 4种情况: root， root + left, root + right, left + root + right, 不要漏掉最后一种left_sum + root.val + right_sum
  2. 全局最大值作为返回值，初始值为负无穷float(‘-inf’)。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
def maxPathSum(self, root: TreeNode) -> int:
	_, path_gsum = self.dfs(root)
	return path_gsum

def dfs(self, root: TreeNode) -> int:
	if not root:
       return float('-inf'), float('-inf')
	left_sum, left_gsum = self.dfs(root.left)
	right_sum, right_gsum = self.dfs(root.right)
	max_path_sum = max(left_sum + root.val, right_sum + root.val, root.val)
	max_path_gsum = max(max_path_sum, left_gsum, right_gsum, left_sum + root.val + right_sum)
	return max_path_sum, max_path_gsum

算法II迭代解题思路：

由上述算法看出，属于后序遍历，因为先left, right, 再计算root。所以用后序遍历模板。然后定义dp[root]为以root为结束点的最大路径值，这与上题也一样。
递归式为

1
dp[node] = max(dp[node.left] + node.val, dp[node.right] + node.val, node.val)

res为全局最大值，也和上述一致
max_path_sum = dp[node]
res = left_gsum, right_gsum

注意事项：

  1. occurrence先加再比较

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def maxPathSum2(self, root: TreeNode) -> int:
	it, stack, res = root, [], float('-inf')
	dp = collections.defaultdict(int)
	while it:
		stack.append((it, 0))
		it = it.left

	while stack:
		node, occurrence = stack.pop()
		occurrence += 1 # remember
		if occurrence == 2:
			dp[node] = max(dp[node.left] + node.val, dp[node.right] + node.val, node.val)
			res = max(res, dp[node], dp[node.left] + node.val + dp[node.right])
			continue
		else:
			stack.append((node, occurrence))
		if node.right:
			n = node.right
			while n:
				stack.append((n, 0))
				n = n.left
	return res

Follow-up

若path的起始点均为叶子节点

解题思路：

叶子节点要返回值，gsum为无穷小。修改max_path_sum和max_path_gsum公式，不含单独root以及gsum不含以root为终点的路径。
还有路径可能不存在

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def maxPathSum_fromleaf2leaf(self, root: TreeNode) -> int:
	path_sum, path_gsum = self.dfs_leaf(root)
	return path_gsum if path_gsum != float('-inf') else None

def dfs_leaf(self, root: TreeNode) -> int:
	if not root:
		return float('-inf'), float('-inf')
	if not root.left and not root.right:
		return root.val, float('-inf') # remember no gsum
	left_sum, left_gsum = self.dfs_leaf(root.left)
	right_sum, right_gsum = self.dfs_leaf(root.right)
	max_path_sum = max(left_sum + root.val, right_sum + root.val)
	max_path_gsum = max(left_gsum, right_gsum, left_sum + root.val + right_sum)
	return max_path_sum, max_path_gsum

Follow-up 2

若path的起始点均为叶子节点且只能从某些特定的叶子节点出发和结束

解题思路：

同上，只不过加入条件root.val in endnodes

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def maxPathSum_fromSpecificNodes(self, root: TreeNode, endnodes) -> int:
	path_sum, path_gsum = self.dfs_end_nodes(root, set(endnodes))
	return path_gsum if path_gsum != float('-inf') else None

def dfs_end_nodes(self, root: TreeNode, endnodes) -> int:
	if not root:
		return float('-inf'), float('-inf')
	if not root.left and not root.right and root.val in endnodes:
		return root.val, float('-inf') # remember no gsum
	left_sum, left_gsum = self.dfs_end_nodes(root.left, endnodes)
	right_sum, right_gsum = self.dfs_end_nodes(root.right, endnodes)
	max_path_sum = max(left_sum + root.val, right_sum + root.val)
	max_path_gsum = max(left_gsum, right_gsum, left_sum + root.val + right_sum)
	return max_path_sum, max_path_gsum

Follow-up 3

若path的起始点可为任意节点且只能从某些特定的叶子节点出发和结束

解题思路：

若起始节点为非叶子节点，注意将表达式修改为原始表达式。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def maxPathSum_fromSpecificNodes2(self, root: TreeNode, endnodes) -> int:
	path_sum, path_gsum = self.dfs_end_nodes2(root, set(endnodes))
	return path_gsum if path_gsum != float('-inf') else None

def dfs_end_nodes2(self, root: TreeNode, endnodes) -> int:
	if not root:
		return float('-inf'), float('-inf')
	if not root.left and not root.right and root.val in endnodes:
		return root.val, float('-inf') # remember no gsum
	left_sum, left_gsum = self.dfs_end_nodes2(root.left, endnodes)
	right_sum, right_gsum = self.dfs_end_nodes2(root.right, endnodes)
	max_path_sum = max(left_sum + root.val, right_sum + root.val)
	if root.val in endnodes:
		max_path_sum = max(max_path_sum, root.val)
	max_path_gsum = max(left_gsum, right_gsum, left_sum + root.val + right_sum)
	if root.val in endnodes:
		max_path_gsum = max(max_path_gsum, max_path_sum)
	return max_path_sum, max_path_gsum

注意事项：

  1. 4种情况
  2. 定义全局变量来比较最大值，因为左到右情况不能返回。全局变量初始值为负无穷。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int gsum = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root){
	gsum = 0;
	int a = max(root);
	return gsum;
}
public int max(TreeNode root){
	if(root==null)
		return 0;
	int lmax = max(root.left);
	int rmax = max(root.right);
	int sum = Math.max(Math.max(lmax, rmax)+root.val,root.val);
	gsum = Math.max(Math.max(gsum, sum), lmax+root.val+rmax);
	return sum;
}

算法分析：

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

相关题目：

LeetCode 112 Path Sum
LeetCode 124 Binary Tree Maximum Path Sum

Free mock interview