• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            Uriel's Corner

            Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
            posts - 0, comments - 50, trackbacks - 0, articles - 594

            [LeetCode]Path Sum [& ||]-2014.01.18

            Posted on 2014-01-18 18:06 Uriel 閱讀(144) 評論(0)  編輯 收藏 引用 所屬分類: LeetCode
            Path Sum
            給一棵二叉樹和一個整數(shù),二叉樹中每個節(jié)點有個權(quán)值,每條從根節(jié)點到葉節(jié)點的路權(quán)值求和,問是否存在權(quán)值和等于給定數(shù)的
            BFS,記錄權(quán)值和,到葉節(jié)點的時候判斷是否等于給定的數(shù)

             1 /**
             2  * Definition for binary tree
             3  * struct TreeNode {
             4  *     int val;
             5  *     TreeNode *left;
             6  *     TreeNode *right;
             7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
             8  * };
             9  */
            10 class Solution {
            11 public:
            12     struct Que {
            13         int s;
            14         TreeNode *p;
            15     }q[100010];
            16             
            17     bool hasPathSum(TreeNode *root, int sum) {
            18         int l = 0, r = 1, res = 0;
            19         if(root == NULL) return 0;
            20         q[0].p = root;
            21         q[0].s = root->val;
            22         while(l < r) {
            23             if(q[l].p->left == NULL && q[l].p->right == NULL) {
            24                 if(q[l].s == sum) return true;
            25             }
            26             if(q[l].p->left != NULL) {
            27                 q[r].p = q[l].p->left;
            28                 q[r].s = q[l].s + q[r].p->val;
            29                 ++r;
            30             }
            31             if(q[l].p->right != NULL) {
            32                 q[r].p = q[l].p->right;
            33                 q[r].s = q[l].s + q[r].p->val;
            34                 ++r;
            35             }
            36             ++l;
            37         }
            38         return false;
            39     }
            40 };

            Path Sum II
            上一題的加強版,要輸出所有權(quán)值和等于給定整數(shù)的路徑,開個變量記錄隊列元素之前一個遍歷的節(jié)點,到葉子節(jié)點時若權(quán)值和等于給定數(shù),則遞歸找出路徑

             1 /**
             2  * Definition for binary tree
             3  * struct TreeNode {
             4  *     int val;
             5  *     TreeNode *left;
             6  *     TreeNode *right;
             7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
             8  * };
             9  */
            10 class Solution {
            11 public:
            12     struct Que {
            13         int s, fa;
            14         TreeNode *p;
            15     }q[100010];
            16             
            17     vector<vector<int> > pathSum(TreeNode *root, int sum) {
            18         int l = 0, r = 1;
            19         vector<vector<int> > res;
            20         res.clear();
            21         if(root == NULL) return res;
            22         q[0].p = root;
            23         q[0].fa = -1;
            24         q[0].s = root->val;
            25         while(l < r) {
            26             if(q[l].p->left == NULL && q[l].p->right == NULL) {
            27                 if(q[l].s == sum) {
            28                     vector<int> t;
            29                     int tp = l;
            30                     while(tp >= 0) {
            31                         t.push_back(q[tp].p->val);
            32                         tp = q[tp].fa;
            33                     }
            34                     reverse(t.begin(), t.end());
            35                     res.push_back(t);
            36                 }
            37             }
            38             if(q[l].p->left != NULL) {
            39                 q[r].p = q[l].p->left;
            40                 q[r].fa = l;
            41                 q[r].s = q[l].s + q[r].p->val;
            42                 ++r;
            43             }
            44             if(q[l].p->right != NULL) {
            45                 q[r].p = q[l].p->right;
            46                 q[r].fa = l;
            47                 q[r].s = q[l].s + q[r].p->val;
            48                 ++r;
            49             }
            50             ++l;
            51         }
            52         return res;
            53     }
            54 };
            久久久无码精品亚洲日韩软件| 色婷婷噜噜久久国产精品12p| 久久久久国产精品人妻| 久久中文字幕人妻熟av女| 7777精品伊人久久久大香线蕉| 蜜桃麻豆WWW久久囤产精品| 久久精品中文騷妇女内射| 久久香蕉国产线看观看99| 久久中文字幕无码专区| 色综合久久综合中文综合网| 国产成人精品久久| 精品人妻伦九区久久AAA片69| 香港aa三级久久三级| 日产精品久久久久久久| 久久精品国产只有精品66| 午夜天堂精品久久久久| 色诱久久av| 青青青国产成人久久111网站| 久久久久亚洲av成人网人人软件| 亚洲成色999久久网站| 人妻无码αv中文字幕久久| 色婷婷狠狠久久综合五月| 国产精品青草久久久久福利99| 午夜天堂av天堂久久久| 热99RE久久精品这里都是精品免费 | 精品久久国产一区二区三区香蕉| 亚洲国产精品无码久久一线| 中文字幕无码久久久| 国产69精品久久久久99| 久久99国产亚洲高清观看首页 | 精品久久人妻av中文字幕| 2019久久久高清456| 午夜精品久久久久久| 久久亚洲国产精品123区| 国产999精品久久久久久| 精品久久久久久无码国产| 国产激情久久久久影院| 久久精品一区二区影院| 精品人妻伦一二三区久久 | 国产精品久久久久jk制服| 久久国产精品99精品国产|