leetcode113. Path Sum II

Eirunye 發(fā)布于2019-08-15 10:51 / 1186人閱讀

摘要：題目要求從樹中找到所有符合條件的從根節(jié)點(diǎn)到葉節(jié)點(diǎn)路徑，條件即為樹上所有節(jié)點(diǎn)值的和等于目標(biāo)值?？梢詤⒖歼@篇博客思路和代碼其實(shí)這里本質(zhì)上的思路并沒有改變，還是采用深度優(yōu)先算法，采用自頂向下遞歸的方式將符合條件的結(jié)果放入結(jié)果集中。

題目要求

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]
]

從樹中找到所有符合條件的從根節(jié)點(diǎn)到葉節(jié)點(diǎn)路徑，條件即為樹上所有節(jié)點(diǎn)值的和等于目標(biāo)值。
Path Sum I可以參考這篇博客

思路和代碼

其實(shí)這里本質(zhì)上的思路并沒有改變，還是采用深度優(yōu)先算法，采用自頂向下遞歸的方式將符合條件的結(jié)果放入結(jié)果集中。

    public List> pathSum(TreeNode root, int sum) {
        List> result = new ArrayList>();
        pathSum(root, sum, new ArrayList(), result);
        return result;
    }
    
    public void pathSum(TreeNode root, int sum, List path, List> result){
        if(root==null) return;
        sum -= root.val;
        if(isLeaf(root) && sum==0){
            path.add(root.val);
            result.add(new ArrayList(path));
            path.remove(path.size()-1);
            return;
        }
        path.add(root.val);
        pathSum(root.left, sum, path, result);
        pathSum(root.right, sum, path, result);
        path.remove(path.size()-1);
        
        
    }
    
    private boolean isLeaf(TreeNode node){
        return node!=null && node.left==null && node.right==null;
    }

想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~