[LeetCode] 113. Path Sum II 二叉樹(shù)路徑之和之二

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

 5
/ \
4   8
/      / \
11  13  4
/  \         / \
7    2     5   1

return

[
[5,4,11,2],
[5,8,4,5]
]

這道二叉樹(shù)路徑之和在之前那道題 Path Sum 的基礎(chǔ)上又需要找出路徑，但是基本思想都一樣，還是需要用深度優(yōu)先搜索 DFS，只不過(guò)數(shù)據(jù)結(jié)構(gòu)相對(duì)復(fù)雜一點(diǎn)，需要用到二維的 vector，而且每當(dāng) DFS 搜索到新結(jié)點(diǎn)時(shí)，都要保存該結(jié)點(diǎn)。而且每當(dāng)找出一條路徑之后，都將這個(gè)保存為一維 vector 的路徑保存到最終結(jié)果二維 vector 中。并且，每當(dāng) DFS 搜索到子結(jié)點(diǎn)，發(fā)現(xiàn)不是路徑和時(shí)，返回上一個(gè)結(jié)點(diǎn)時(shí)，需要把該結(jié)點(diǎn)從一維 vector 中移除，參見(jiàn)代碼如下：

解法一：

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> res;
        vector<int> out;
        helper(root, sum, out, res);
        return res;
    }
    void helper(TreeNode* node, int sum, vector<int>& out, vector<vector<int>>& res) {
        if (!node) return;
        out.push_back(node->val);
        if (sum == node->val && !node->left && !node->right) {
            res.push_back(out);
        }
        helper(node->left, sum - node->val, out, res);
        helper(node->right, sum - node->val, out, res);
        out.pop_back();
    }
};

下面這種方法是迭代的寫(xiě)法，用的是中序遍歷的順序，參考之前那道 Binary Tree Inorder Traversal，中序遍歷本來(lái)是要用棧來(lái)輔助運(yùn)算的，由于要取出路徑上的結(jié)點(diǎn)值，所以用一個(gè) vector 來(lái)代替 stack，首先利用 while 循環(huán)找到最左子結(jié)點(diǎn)，在找的過(guò)程中，把路徑中的結(jié)點(diǎn)值都加起來(lái)，這時(shí)候取出 vector 中的尾元素，如果其左右子結(jié)點(diǎn)都不存在且當(dāng)前累加值正好等于 sum 了，將這條路徑取出來(lái)存入結(jié)果 res 中，下面的部分是和一般的迭代中序?qū)懛ㄓ兴煌牡胤?，由于中序遍歷的特點(diǎn)，遍歷到當(dāng)前結(jié)點(diǎn)的時(shí)候，是有兩種情況的，有可能此時(shí)是從左子結(jié)點(diǎn)跳回來(lái)的，此時(shí)正要去右子結(jié)點(diǎn)，則當(dāng)前的結(jié)點(diǎn)值還是算在路徑中的；也有可能當(dāng)前是從右子結(jié)點(diǎn)跳回來(lái)的，并且此時(shí)要跳回上一個(gè)結(jié)點(diǎn)去，此時(shí)就要減去當(dāng)前結(jié)點(diǎn)值，因?yàn)槠湟呀?jīng)不屬于路徑中的結(jié)點(diǎn)了。為了區(qū)分這兩種情況，這里使用一個(gè)額外指針 pre 來(lái)指向前一個(gè)結(jié)點(diǎn)，如果右子結(jié)點(diǎn)存在且不等于 pre，直接將指針移到右子結(jié)點(diǎn)，反之更新 pre 為 cur，cur 重置為空，val 減去當(dāng)前結(jié)點(diǎn)，st 刪掉最后一個(gè)結(jié)點(diǎn)，參見(jiàn)代碼如下：

解法二：

class Solution {
public:
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> res;
        vector<TreeNode*> st;
        TreeNode *cur = root, *pre = nullptr;
        int val = 0;
        while (cur || !st.empty()) {
            while (cur) {
                st.push_back(cur);
                val += cur->val;
                cur = cur->left;
            }
            cur = st.back(); 
            if (!cur->left && !cur->right && val == sum) {
                vector<int> v;
                for (auto &a : st) v.push_back(a->val);
                res.push_back(v);
            }
            if (cur->right && cur->right != pre) {
                cur = cur->right;
            } else {
                pre = cur;
                val -= cur->val;
                st.pop_back();
                cur = nullptr;
            }
        }
        return res;
    }
};

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(113.二叉樹(shù)路徑之和之二)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)二叉樹(shù)路徑之和之二內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論