• <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 閱讀(148) 評論(0)  編輯 收藏 引用 所屬分類: LeetCode
            Path Sum
            給一棵二叉樹和一個整數,二叉樹中每個節點有個權值,每條從根節點到葉節點的路權值求和,問是否存在權值和等于給定數的
            BFS,記錄權值和,到葉節點的時候判斷是否等于給定的數

             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
            上一題的加強版,要輸出所有權值和等于給定整數的路徑,開個變量記錄隊列元素之前一個遍歷的節點,到葉子節點時若權值和等于給定數,則遞歸找出路徑

             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 };
            热re99久久精品国产99热| 久久久www免费人成精品| 亚洲午夜久久久久久久久久| 日本久久中文字幕| 午夜福利91久久福利| 欧美日韩中文字幕久久久不卡| 久久久国产精华液| 久久人人爽人人爽AV片| 久久综合色区| 久久成人小视频| 国产色综合久久无码有码| 人妻无码αv中文字幕久久| 久久国产精品无码HDAV| 97久久精品无码一区二区天美| 久久精品9988| 亚洲国产成人精品91久久久 | 久久精品国产亚洲AV蜜臀色欲 | 国产精品女同久久久久电影院| 久久久噜噜噜久久中文福利| 久久精品一区二区三区不卡| 久久夜色精品国产www| 一本色综合网久久| 2020最新久久久视精品爱| 久久午夜免费视频| 久久er热视频在这里精品| 亚洲?V乱码久久精品蜜桃| 国产成人久久激情91| 中文字幕久久精品| 久久综合久久综合久久综合| 久久久这里有精品| 色综合合久久天天综合绕视看| 久久久精品国产免大香伊| 亚洲国产成人久久精品动漫| 日本五月天婷久久网站| 国产叼嘿久久精品久久| 久久精品www人人爽人人| 一本色综合久久| 久久精品国产精品亜洲毛片 | 国内精品久久久久久久97牛牛| 久久精品国产精品亚洲| 国产午夜久久影院|