程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> [leetcode]Path Sum

[leetcode]Path Sum

編輯:關於C++

題目:

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.

分析:
題目是要看給定的樹中是否存在一條從根到葉節點的路徑,該路徑上所有節點上值的和相加為給定的值。可以采用遞歸的思想,每次看該節點的右子樹節點的值是否為當前sum減去當前節點的值,左子樹也進行同樣的處理。
代碼:

class Solution {
public:

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

};
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved