257. Binary Tree Paths

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

All root-to-leaf paths are:

["1->2->5", "1->3"]

S: dfs

    vector<string> binaryTreePaths(TreeNode* root) {
        vector<string> result;
        if (!root) {
            return result;
        }
        bfs(root, "", result);
        return result;
    }

    void bfs(TreeNode* root, string before, vector<string>& result) {
        before += to_string(root->val);
        if (!root->left && !root->right) {
            result.push_back(before);
            return;
        }
        if (root->left) {
            bfs(root->left, before + "->", result);
        }
        if (root->right) {
            bfs(root->right, before + "->", result);
        }
    }

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.

S: DFS

想清楚path的定义，左子树右子树和父节点中只能选两支

    int maxPathSum(TreeNode* root) {
        int result = INT_MIN;
        maxSum(root, result);
        return result;
    }

    int maxSum(TreeNode* root, int& result) {
        if (!root) return 0;
        int left = maxSum(root->left, result);
        int right = maxSum(root->right, result);
        int sum = root->val;
        if (left > 0) {
            sum += left;
        }
        if (right > 0) {
            sum += right;
        }
        if (sum > result) {
            result = sum;
        }
        sum = root->val;
        sum += max(max(left, right), 0);
        return sum;
    }

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.

S: DFS

    bool hasPathSum(TreeNode* root, int sum) {
        if (!root) return false;
        if (!root->left && !root->right) {
          return sum == root->val;
        }
        else {
          return hasPathSum(root->left, sum - root->val) ||
                 hasPathSum(root->right, sum - root->val);
        }
    }

113. Path Sum II

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

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

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

return

[
   [5,4,11,2],
   [5,8,4,5]
]

S: DFS, backtracing

传递reference比传递原vector要快很多，每次push再pop

    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> result;
        vector<int> path;
        pathSum(root, result, path, sum);
        return result;
    }

    void pathSum(TreeNode* root, vector<vector<int>>& result, vector<int>& path, int sum) {
        if(!root) return;
        path.push_back(root->val);
        if (!root->left && !root->right && sum == root->val) {
            result.push_back(path);
        }
        pathSum(root->left, result, path, sum - root->val);
        pathSum(root->right, result, path, sum - root->val);
        path.pop_back();
    }

543.Diameter of Binary Tree

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Example:

Given a binary tree

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

S: recursion

    int diameterOfBinaryTree(TreeNode* root) {
        int maxPath = 0;
        dfs(root, maxPath);
        return maxPath;
    }

    int dfs(TreeNode* root, int& maxPath) {
        if (!root) {
            return 0;
        }
        int left = dfs(root->left, maxPath);
        int right = dfs(root->right, maxPath);
        maxPath = max(maxPath, left + right);
        return max(left, right) + 1;
    }

404. Sum of Left Leaves

Find the sum of all left leaves in a given binary tree.

Example:

    3
   / \
  9  20
    /  \
   15   7

There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.