376. 二叉树的路径和

最近忙着做React分享研究,好久没刷算法题了。

题目

给定一个二叉树,找出所有路径中各节点相加总和等于给定 目标值 的路径。

一个有效的路径,指的是从根节点到叶节点的路径。
http://www.lintcode.com/zh-cn/problem/binary-tree-path-sum/

分析

几个重点:

  1. 限定了是从根节点到叶子节点的和
  2. 节点的值有可能是负数,因此如果到某个节点累计和超过目标值时,仍需继续探索

思路还是很清晰的,遍历这棵树,如果节点是叶子节点,则查看求和是否满足目标值要求,若满足,就找到一组解。若非叶子节点,则将当前节点的值保存到一个队列中,继续探索其子节点。

代码


/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */



public class Solution {
    
    List clone(List list) {
        List nlist = new ArrayList<>();
        for (Integer i : list) {
            nlist.add(i.intValue());
        }
        return nlist;
    }
    
    boolean isLeaf(TreeNode node) {
        if (node != null && node.left == null && node.right == null) return true;
        return false;
    }
    
    void findPath(
        TreeNode node, 
        List list, 
        int total, 
        int target,
        List> result){
        
        if (node == null) return;
        
        total = node.val + total;
            
        if(isLeaf(node)) {

            if(total == target) {
                List nlist = clone(list);
                nlist.add(node.val);
                result.add(nlist);
                return;
            }
            
            return;
        } else {
           
            list.add(node.val);
            
            if(node.left != null && node.right != null) {
                List rlist = clone(list);
                findPath(node.left, list, total, target, result);
                findPath(node.right, rlist, total, target, result);
                return;
            } else {
                node = node.left == null ? node.right : node.left;
                findPath(node, list, total, target, result);
                return;
            }
        }
    }
    /*
     * @param root: the root of binary tree
     * @param target: An integer
     * @return: all valid paths
     */
    public List> binaryTreePathSum(TreeNode root, int target) {
        List> result = new ArrayList<>();

        if (root == null) return result;

        // write your code here
        List list = new ArrayList<>();
        
        findPath(root, list, 0, target, result);
        
        return result;
    }
}
Show Comments

Get the latest posts delivered right to your inbox.