leetcode 二叉树 路径总和

package com.karl.study.leetcode;

public class BinaryTreePathSum {
    /**
     * 从2叉树的根开始，判断是否存在一个到叶子节点的路径，路径上所有节点值的和为22
     *            5
     *          /   \
     *        4       8
     *       /       /  \
     *     11       13    4
     *    /  \              \
     *  7     2              1
     * 路径 ： 5->4->11->2的总和为22，则存在要求的路径。
     */
    public static void main(String[] args)  {
        Node root = buildBinaryTree();
        try {
            checkExist(root, 0, 22);
        } catch (Exception e) {
            if("find".equals(e.getMessage())) {
                System.out.println("find");
            }
        }
    }

    private static void checkExist(Node root, int sum, final int checkValue) throws Exception {
        if(root.left != null) {
            checkExist(root.left, sum + root.value, checkValue);
        }
        if(root.right != null) {
            checkExist(root.right, sum + root.value, checkValue);
        }
        if(root.left == null && root.right == null) {
            System.out.println(sum + root.value);
            if(sum + root.value == checkValue) {
                ////通过抛异常的方式，让程序提前完成， 否则就算找到了，也需要全部遍历完成
                throw new Exception("find");
            }
        }
    }

    static class Node{
        Node left;
        Node right;
        int value;

        public Node(int value) {
            this.value = value;
        }
    }

    private static Node buildBinaryTree() {
        Node root = new Node(5);
        root.left = new Node(4);
        root.right = new Node(8);
        root.left.left = new Node(11);
        root.left.left.left = new Node(7);
        root.left.left.right = new Node(2);
        root.right.left = new Node(13);
        root.right.right = new Node(4);
        root.right.right.left = new Node(1);
        return root;
    }
}