文档章节

*【九度OJ1368】|【剑指offer25】二叉树中和为某一值的路径

aqia358
 aqia358
发布于 2013/12/25 21:38
字数 640
阅读 120
收藏 0

题目描述:

输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

输入:

每个测试案例包括n+1行:

第一行为2个整数n,k(1<=n<=10000),n表示结点的个数,k表示要求的路径和,结点编号从1到 n。                                                                                                       

接下来有n行。这n行中每行为3个整数vi,leftnode,rightnode,vi表示第i个结点的值,leftnode表示第i个结点的左孩子结点编号,rightnode表示第i个结点的右孩子结点编号,若无结点值为-1。编号为1的结点为根结点。

输出:

对应每个测试案例,先输出“result:”占一行,接下来按字典顺序输出满足条件的所有路径,这些路径由结点编号组成,输出格式参照输出样例。

样例输入:
5 22
10 2 3
5 4 5
12 -1 -1
4 -1 -1
7 -1 -1
1 5
1 -1 -1
样例输出:
result:
A path is found: 1 2 5
A path is found: 1 3
result:
解:首先要想到的是通过遍历可以找到所有路径,按照先序遍历的思路,先将经过的左节点入栈,如果是进的是叶子节点,则判断和是否符合要求,否和要求打印路径将该结点出栈,不否和要求直接将结点出栈,然后继续遍历
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Stack;
 
public class Main {
    public static int target;
     
    static class Node{
        public int id;
        public int data;
        public Node left;
        public Node right;
        public Node(int id){
            this.id = id;
        }
    }
    public static Node find(int id, Node node){
        if(node != null){
            if(node.id == id)
                return node;
            Node l = find(id, node.left);
            Node r = find(id, node.right);
            if(l != null){
                return l;
            }else if(r != null){
                return r;
            }else
                return null;
        }else{
            return null;
        }
    }
    public static void search(Node node, Stack<Integer> stack, int sum){
        if(node == null || node.id == -1){
            return;
        }else{
            sum += node.data;
            stack.push(node.id);
            search(node.left, stack, sum);
            search(node.right, stack, sum);
            if(sum == target && node.left.id == -1 && node.right.id == -1){
                System.out.print("A path is found:");
                for(int i:stack){
                    System.out.print(" "+i);
                }
                System.out.println();
            }
            stack.pop();
        }
    }
     
    public static void main(String[] args) throws IOException {
         
        StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        while(st.nextToken() != StreamTokenizer.TT_EOF){
            int n = (int)st.nval;
            st.nextToken();
            Main.target = (int)st.nval;
            Node root = new Node(1);
            for(int i = 1; i <= n; i++){
                Node node = Main.find(i, root);
                st.nextToken();
                node.data = (int)st.nval;
                st.nextToken();
                int l = (int)st.nval;
                st.nextToken();
                int r = (int)st.nval;
                if(l > r){
                    node.left = new Node(r);
                    node.right = new Node(l);
                }else{
                    node.left = new Node(l);
                    node.right = new Node(r);
                }
            }
            System.out.println("result:");
            Main.search(root, new Stack<Integer>(), 0);
        }
    }
 
}



注:第一个案例没通过



© 著作权归作者所有

共有 人打赏支持
aqia358
粉丝 6
博文 82
码字总数 30297
作品 0
海淀
程序员
[算法总结] 20 道题搞定 BAT 面试——二叉树

本文首发于我的个人博客:尾尾部落 0. 几个概念 完全二叉树:若二叉树的高度是h,除第h层之外,其他(1h-1)层的节点数都达到了最大个数,并且第h层的节点都连续的集中在最左边。想到点什么没...

繁著
09/04
0
0
python剑指offer66题

二维数组的查找 替换空格 从头到尾打印链表 重建二叉树 用两个栈实现队列 选择数组中的最小数字 斐波那契数列 跳台阶 变态跳台阶 矩形覆盖 二进制中1的个数 数值的整数次方 调整数组顺序使奇...

lyy0905
06/03
0
0
[剑指offer] 二叉树中和为某一值的路径

题目描述 输入一颗二叉树和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。 解题思路 用前序遍历的方式访...

繁著
07/01
0
0
算法之路

最近在GitHub上看到的某位学友的算法学习规划,贴过来与各位共勉。有新的内容可以文末留言补充。 学习方法 把所有经典算法写一遍 看算法有关源码 加入算法学习社区,相互鼓励学习 看经典书籍...

李序锴
2017/11/08
0
0
数据结构与算法(3)——树(二叉、二叉搜索树)

前言:题图无关,现在开始来学习学习树相关的知识 前序文章: 数据结构与算法(1)——数组与链表(https://www.jianshu.com/p/7b93b3570875) 数据结构与算法(2)——栈和队列(https://www.ji...

我没有三颗心脏
07/11
0
0

没有更多内容

加载失败,请刷新页面

加载更多

聊聊clean code

clean code,顾名思义就是整洁的代码,或者说清晰、漂亮的代码,相信大多数工程师都希望自己能写出这样的代码。 也许这是个千人千面的话题,每个工程师都有自己的理解。比如我,从一个天天被...

Skqing
28分钟前
3
0
redis连接报错—— (error) NOAUTH Authentication required.

1.redis报认证错误 redis客户端连接成功,但是操作报异常——(error) NOAUTH Authentication required 错误的含义是说你没有认证,说明没有使用密码连接 redis-cli -h 127.0.0.1 -p 6379 -a ...

啊哈关关
34分钟前
2
0
地理位置坐标标准以及转换

/** * 地理位置坐标标准以及转换 * * 1.WGS-84原始坐标系,一般用国际GPS纪录仪记录下来的经纬度,通过GPS定位拿到的原始经纬度,Google和高德地图定位的的经纬度(国外)都是基于W...

葉者
37分钟前
2
0
Generator-ES6

基本概念 Generator 函数是 ES6 提供的一种异步编程解决方案,语法行为与传统函数完全不同。 Generator 函数有多种理解角度。语法上,首先可以把它理解成,Generator 函数是一个状态机,封装...

简心
55分钟前
6
0
FullCalendar日历插件说明文档

普通显示设置 属性 描述 默认值 header 设置日历头部信息。 如果设置为false,则不显示头部信息。包括left,center,right左中右三个位置,每个位置都可以对应以下不同的配置: title: 显示当...

ada_young
56分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部