[剑指Offer]-二叉树中和为某一的的路径

题目描述

输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。
例如下图，输入的二叉树和整数22，则打印出两条路径，第一条路径包含节点10、12；第二条路径包含节点10、5和7 。

这里存在回退去遍历另一节点，所以考虑使用栈来存储元素。

解题思路

• 当遍历到一个节点的时候将当前节点入栈，同时currentSum+=root.node_value。
• 如果当前节点没有子节点同时currentSum等于目标值则栈元素遍历弹出。
• 否则递归入栈左右子树继续调用。

算法图解

参考代码：

package offer;

import java.util.Stack;

/**
 * 二叉树中和为某一值得路径
 */
public class Offer34 {
    public static void main(String[] args) {
        BinaryTreeNode root = new BinaryTreeNode(10);
        BinaryTreeNode node1 = new BinaryTreeNode(5);
        BinaryTreeNode node2 = new BinaryTreeNode(12);
        BinaryTreeNode node3 = new BinaryTreeNode(4);
        BinaryTreeNode node4 = new BinaryTreeNode(7);
        root.leftTree = node1;
        root.rightTree = node2;
        node1.leftTree = node3;
        node1.rightTree = node4;
        int target = 22;
        Stack<Integer> path=new Stack<Integer>();
        findPath(root, target,path, 0);
    }

    private static void findPath(BinaryTreeNode root, int target, Stack<Integer> path, int currentSum) {
        if(root==null){
            return;
        }
        currentSum+=root.node_value;
        path.push(root.node_value);
        boolean isLeaf=root.leftTree==null&&root.rightTree==null;
        if(isLeaf&&currentSum==target){
           while (!path.isEmpty()){
               Integer poll = path.pop();
               System.out.println(poll+" ");
           }
            System.exit(0);
        }
        else{
            if(root.leftTree!=null){
                findPath(root.leftTree,target,path,currentSum);
            }
            if(root.rightTree!=null){
                findPath(root.rightTree,target,path,currentSum);
            }
            path.pop();
        }

    }
}

附录

该题源码在我的 ????Github 上面！