//C++ class Solution { public: int rootSum(TreeNode* root, int targetSum) { if (!root) { return 0; }
int ret = 0; if (root->val == targetSum) { ret++; }
ret += rootSum(root->left, targetSum - root->val); ret += rootSum(root->right, targetSum - root->val); return ret; }
int pathSum(TreeNode* root, int targetSum) { if (!root) { return 0; } int ret = rootSum(root, targetSum); ret += pathSum(root->left, targetSum); ret += pathSum(root->right, targetSum); return ret; } };
保持：如果 i=k 时性质成立，即第 k 轮中出队 sk 的元素是第 k 层的所有元素，并且顺序从左到右。因为对树进行广度优先搜索的时候由低 k 层的点拓展出的点一定也只能是 k+1 层的点，并且 k+1 层的点只能由第 k 层的点拓展到，所以由这 sk 个点能拓展到下一层所有的 sk+1 个点。又因为队列的先进先（FIFO）特性，既然第 k 层的点的出队顺序是从左向右，那么第 k+1 层也一定是从左向右。至此，我们已经可以通过数学归纳法证明循环不变式的正确性。
//Java class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> ret = new ArrayList<List<Integer>>(); if (root == null) { return ret; }
Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.offer(root); while (!queue.isEmpty()) { List<Integer> level = new ArrayList<Integer>(); int currentLevelSize = queue.size(); for (int i = 1; i <= currentLevelSize; ++i) { TreeNode node = queue.poll(); level.add(node.val); if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } ret.add(level); } return ret; } }
最后的算法流程为：我们定义一个递归函数 depth(node) 计算 dnoded ，函数返回该节点为根的子树的深度。先递归调用左儿子和右儿子求得它们为根的子树的深度 L 和 R ，则该节点为根的子树的深度即为 max(L,R)+1，该节点的 dnoded 值为 L+R+1 递归搜索每个节点并设一个全局变量 ans 记录 dnoded 的最大值，最后返回 ans-1 即为树的直径。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
//Java class Solution { int ans; public int diameterOfBinaryTree(TreeNode root) { ans = 1; depth(root); return ans - 1; } public int depth(TreeNode node) { if (node == null) { return 0; // 访问到空节点了，返回0 } int L = depth(node.left); // 左儿子为根的子树的深度 int R = depth(node.right); // 右儿子为根的子树的深度 ans = Math.max(ans, L+R+1); // 计算d_node即L+R+1 并更新ans return Math.max(L, R) + 1; // 返回该节点为根的子树的深度 } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
//C++ class Solution { int ans; int depth(TreeNode* rt){ if (rt == NULL) { return 0; // 访问到空节点了，返回0 } int L = depth(rt->left); // 左儿子为根的子树的深度 int R = depth(rt->right); // 右儿子为根的子树的深度 ans = max(ans, L + R + 1); // 计算d_node即L+R+1 并更新ans return max(L, R) + 1; // 返回该节点为根的子树的深度 } public: int diameterOfBinaryTree(TreeNode* root) { ans = 1; depth(root); return ans - 1; } };
复杂度分析
时间复杂度：O(N)，其中 N 为二叉树的节点数，即遍历一棵二叉树的时间复杂度，每个结点只被访问一次。
//Java class Solution { private Map<Integer, Integer> indexMap;
public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) { if (preorder_left > preorder_right) { return null; }
public TreeNode buildTree(int[] preorder, int[] inorder) { int n = preorder.length; // 构造哈希映射，帮助我们快速定位根节点 indexMap = new HashMap<Integer, Integer>(); for (int i = 0; i < n; i++) { indexMap.put(inorder[i], i); } return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1); } }
复杂度分析
时间复杂度：O(n)，其中 n 是树中的节点个数。
空间复杂度：O(n)，除去返回的答案需要的 O(n) 空间之外，我们还需要使用 O(n) 的空间存储哈希映射，以及 O(h)（其中 h 是树的高度）的空间表示递归时栈空间。这里 h<n，所以总空间复杂度为 O(n)。
（2）迭代
思路及算法
迭代法是一种非常巧妙的实现方法。迭代法的实现基于以下两点发现。
如果将中序遍历反序，则得到反向的中序遍历，即每次遍历右孩子，再遍历根节点，最后遍历左孩子。
如果将后序遍历反序，则得到反向的前序遍历，即每次遍历根节点，再遍历右孩子，最后遍历左孩子。
「反向」的意思是交换遍历左孩子和右孩子的顺序，即反向的遍历中，右孩子在左孩子之前被遍历。
对于后序遍历中的任意两个连续节点 u 和 v（在后序遍历中，u 在 v 的前面），根据后序遍历的流程，我们可以知道 u 和 v 只有两种可能的关系：
u 是 v 的右儿子。这是因为在遍历到 u 之后，下一个遍历的节点就是 u 的双亲节点，即 v；
v 没有右儿子，并且 u 是 v 的某个祖先节点（或者 v 本身）的左儿子。如果 v 没有右儿子，那么上一个遍历的节点就是 v 的左儿子。如果 v 没有左儿子，则从 v 开始向上遍历 v 的祖先节点，直到遇到一个有左儿子（且 v 不在它的左儿子的子树中）的节点 va，那么 u 就是 va 的左儿子。
