［LeetCode］Path Sum-白红宇

［LeetCode］Path Sum

阅读量：2235 次

发布时间：2019-05-09

本文共 977 字，大约阅读时间需要 3 分钟。

思路：

深度搜索（这里采用回溯法）

1，先决条件：找到树根

2，不变式：遍历子node，传递sum和当前和 curSum

3，结束条件：node没有子节点，判断sum 是否等于curSum

4，临界条件：树为空

很简单，一遍过。

/** * Definition for a binary tree node. * struct TreeNode { *     int val; *     TreeNode *left; *     TreeNode *right; *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public:    bool hasPathSum(TreeNode* root, int sum) {        if (root == NULL){            return false;        }        return bfs(root, sum, 0);    }    bool bfs(TreeNode* node, int sum, int curSum){        if(node->left == NULL && node->right == NULL){            return sum == (curSum + node->val);        }else{            if (node->left != NULL){                if ( bfs(node->left, sum, curSum + node->val) ){                    return true;                }            }            if (node->right != NULL){                if ( bfs(node->right, sum, curSum + node->val) ){                    return true;                }            }        }    }};

转载地址：http://mcpbb.baihongyu.com/

你可能感兴趣的文章