有点分情况讨论Dp的意思，对于dp问题我们还是需要分两步分析，首先分析子问题是什么。我们最终的结果是长度为n的树叶中，得到上下上的形式。这个问题可以变为子问题。在长度为n-1的树叶集得到 1. 上下上/上下，这样最后一个只需要保证变为上；这样我们考虑第n-1片叶子，如果n-1是上下上，则n-2需要是 上下或者上下上；如果n-1是上下，则n-2需要是 上上或者上下。
因此实际上由三个大的状态：上，上下，上下上。
class Solution { public int minimumOperations(String leaves) { int n = leaves.length(); int[] dp1 = new int[n]; int[] dp2 = new int[n]; int[] dp3 = new int[n]; dp2[0] = 2; // 设置的大一些，防止出现问题 dp3[0] = 2; if (leaves.charAt(0) == 'y')dp1[0] = 1; else dp1[0] = 0; for (int i = 1; i<n; i++){ if (leaves.charAt(i) == 'y') { dp1[i] = dp1[i-1]+1; dp2[i] = Math.min(dp2[i-1], dp1[i-1]); dp3[i] = Math.min(dp3[i-1], dp2[i-1])+1; } else { dp1[i] = dp1[i-1]; dp2[i] = Math.min(dp2[i-1], dp1[i-1])+1; dp3[i] = Math.min(dp3[i-1], dp2[i-1]); } } return dp3[n-1]; } }基本思路是树形dp，并且很巧妙的用了换根的方法，降低了复杂度。 有一个很好的题解。
我理解的思路就是，首先不可避免的需要遍历一遍树也就是dfs完成，这样可以得到根节点的边数量，然后再遍历一遍各个节点，计算出基于已知根节点情况下，自己的距离之和。
每个大根节点的边数量 = 根节点连接的所有子节点数量+所有子节点作为子树的大根的距离之和。 每个子节点的距离之和 = 当前节点作为子树的大根节点的距离之和 +（父节点 - 当前节点的贡献）
class Solution { // 树形Dp+换根的思路 int[] ans; int[] sz; int[] dp; List<List<Integer>> graph; public int[] sumOfDistancesInTree(int N, int[][] edges) { ans = new int[N]; // 连接的子树中所有子节点的数量 sz = new int[N]; // 作为子树的大根的距离之和 dp = new int[N]; graph = new ArrayList<List<Integer>>(); for (int i = 0; i < N; ++i) { graph.add(new ArrayList<Integer>()); } for (int[] edge: edges) { int u = edge[0], v = edge[1]; graph.get(u).add(v); graph.get(v).add(u); } dfs(0, -1); dfs2(0, -1); return ans; } public void dfs(int u, int f) { sz[u] = 1; dp[u] = 0; for (int v: graph.get(u)) { if (v == f) { continue; } dfs(v, u); dp[u] += dp[v] + sz[v]; sz[u] += sz[v]; } } public void dfs2(int u, int f) { ans[u] = dp[u]; for (int v: graph.get(u)) { if (v == f) { continue; } int pu = dp[u], pv = dp[v]; int su = sz[u], sv = sz[v]; dp[u] -= dp[v] + sz[v]; sz[u] -= sz[v]; dp[v] += dp[u] + sz[u]; sz[v] += sz[u]; dfs2(v, u); dp[u] = pu; dp[v] = pv; sz[u] = su; sz[v] = sv; } } }递归的方法很常见了，这里还是记录下递归方法
# 迭代方法： # 不用反转的 # queue的元素一定是下一个元素的父节点 class Solution: def postorderTraversal(self, root): #''' ans, queue, cur = [], [], root while queue or cur: while cur: queue.append(cur) if cur.left: cur = cur.left else: cur = cur.right cur = queue.pop() ans.append(cur.val) if queue and queue[-1].left == cur: cur = queue[-1].right else: cur = None return ans