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. Note: A leaf is a node with no children.

第一次解法

递归加节点上的值，目标值作为参数加入递归最后进行比较，主要的坑在于是根到叶节点的路径，叶节点就必须保证没有子节点

bool hasPathSum(TreeNode* root, int sum) {
    if (root==NULL) return false;
    return hasPath(root, 0, sum);
}

bool hasPath(TreeNode* root, int sum, int target) {
    if (!root->left&&!root->right) return sum+root->val==target;
    return ((root->left && hasPath(root->left, sum+root->val, target)) | (root->right && hasPath(root->right, sum+root->val, target)));
}

更简洁的解法

逆向思维，减到叶节点的时候的值应该等于叶的值

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

#递归 #DFS #tree

110. Balanced Binary Tree 12. Integer to Roman 数字转罗马串