剑指offer-问题25

待我称王封你为后i 2022-05-11 12:26 113阅读 0赞

package offer;
    
    import java.util.ArrayList;
    import java.util.List;
    
    /**
     * offer interview 25
     */
    public class Test25 {
        public static class BinaryTreeNode{
            int value;
            BinaryTreeNode left;
            BinaryTreeNode right;
    
            public BinaryTreeNode(){}
            public BinaryTreeNode(int value){
                this.value = value;
                this.left = null;
                this.right = null;
            }
        }
    
        public static void findPath(BinaryTreeNode root,int expectedSum){
            List<Integer> list = new ArrayList<>();
            if (root != null){
                findPath(root,0,expectedSum,list);
            }
        }
    
        public static void findPath(BinaryTreeNode root, int curSum,int expectedSum,List<Integer> result){
            if (root != null){
                curSum += root.value;
                result.add(root.value);
                if (curSum < expectedSum){
                    findPath(root.left,curSum,expectedSum,result);
                    findPath(root.right,curSum,expectedSum,result);
                }else if(curSum == expectedSum){
                    if (root.left == null && root.right == null){
                        System.out.println(result);
                    }
                }
    
                result.remove(result.size() -1);
    
            }
        }
    
        public static void main(String[] args){
            //            10
            //         /      \
            //        5        12
            //       /\
            //      4  7
            BinaryTreeNode root = new BinaryTreeNode(10);
            root.left = new BinaryTreeNode(5);
            root.right = new BinaryTreeNode(12);
            root.left.left = new BinaryTreeNode(4);
            root.left.right = new BinaryTreeNode(7);
    
            System.out.println("findPath(root,22):");
            findPath(root,22);
    
            System.out.println("findPath(root,15):");
            findPath(root,15);
    
            // 有一条路径上的结点和为19
            System.out.println("findPath(root, 19);");
            findPath(root, 19);
    
    
            //               5
            //              /
            //             4
            //            /
            //           3
            //          /
            //         2
            //        /
            //       1
            BinaryTreeNode root2 = new BinaryTreeNode(5);
            root2.left = new BinaryTreeNode(4);
            root2.left.left = new BinaryTreeNode(3);
            root2.left.left.left = new BinaryTreeNode(2);
            root2.left.left.left.left = new BinaryTreeNode(1);
    
            System.out.println("findPath(root2, 15);");
            findPath(root2, 15);
    
            System.out.println("findPath(root2, 16);");
            findPath(root2, 16);
    
            // 1
            //  \
            //   2
            //    \
            //     3
            //      \
            //       4
            //        \
            //         5
            BinaryTreeNode root3 = new BinaryTreeNode(1);
            root3.right = new BinaryTreeNode(2);
            root3.right.right = new BinaryTreeNode(3);
            root3.right.right.right = new BinaryTreeNode(4);
            root3.right.right.right.right = new BinaryTreeNode(5);
    
            System.out.println("findPath(root3, 15);");
            findPath(root3, 15);
    
            System.out.println("findPath(root3, 16);");
            findPath(root3, 16);
    
            BinaryTreeNode root4 = new BinaryTreeNode(1);
            System.out.println("findPath(root4, 1);");
            findPath(root4, 1);
    
            System.out.println("findPath(root4, 2);");
            findPath(root4, 2);
    
            System.out.println("findPath(null, 0);");
            findPath(null, 0);
    
        }
    
    
    }