【剑指offer-Java版】25二叉树中和为某一值的路径

深碍√TFBOYSˉ_ 2022-08-21 09:40 78阅读 0赞

二叉树中值和为某一值的路径：类似图的深度优先遍历

对于此类问题一直有点弱，多想几次就OK了–主要是不熟悉，毕竟代码写出来之后一看就明白，但是自己想的时候还是有点困难

public class _Q25 {
    
        public void FindPathInTree(BinaryTreeNode<Integer> tree, int expectedSum){
            if(tree == null) return;
    
            Vector<BinaryTreeNode<Integer>> path = new Vector<>();
            int curSum = 0;
    
            FindAndPrintPath(tree, expectedSum, curSum, path);
        }
    
        private void FindAndPrintPath(BinaryTreeNode<Integer> tree, int expectedSum, 
                int curSum, Vector<BinaryTreeNode<Integer>> path){
    
            if(tree == null) return;
    
            curSum = curSum + tree.value;
            path.add(tree);
    
            if(curSum == expectedSum && tree.leftChild == null && tree.rightChild == null){
                for(int i=0; i<path.size(); i++){
                    System.out.print(path.get(i).value + " ");
                }
                System.out.println();
            }
    
            if(tree.leftChild != null) FindAndPrintPath(tree.leftChild, expectedSum, curSum, path);
            if(tree.rightChild != null) FindAndPrintPath(tree.rightChild, expectedSum, curSum, path);
    
            path.remove(path.size() - 1); // 回溯
        }
        }

测试代码：

public class _Q25Test extends TestCase {
        
    
        _Q25 printTreePath = new _Q25();
    
        public void test(){
            BinaryTreeNode<Integer> root = new BinaryTreeNode<>();
            BinaryTreeNode<Integer> node1 = new BinaryTreeNode<>();
            BinaryTreeNode<Integer> node2 = new BinaryTreeNode<>();
            BinaryTreeNode<Integer> node3 = new BinaryTreeNode<>();
            BinaryTreeNode<Integer> node4 = new BinaryTreeNode<>();
    
            root.value = 10;
            node1.value = 5;
            node2.value = 12;
            node3.value = 4;
            node4.value = 7;
    
            root.leftChild = node1;
            root.rightChild = node2;
            node1.leftChild = node3;
            node1.rightChild = node4;
    
            node2.leftChild = null; node2.rightChild = null;
            node3.leftChild = null; node3.rightChild = null;
            node4.leftChild = null; node4.rightChild = null;
    
            printTreePath.FindPathInTree(root, 22);
        }
        }