文档章节

*【九度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
剑指offer 25. 二叉树中和为某一值的路径

原题 输入一颗二叉树的跟节点和一个整数,打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中,...

dby_freedom
11/05
0
0
算法之路

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

李序锴
2017/11/08
0
0

没有更多内容

加载失败,请刷新页面

加载更多

程序中设置MySQL的默认值

import com.alibaba.fastjson.JSON;import java.beans.PropertyDescriptor;import java.lang.annotation.*;import java.lang.reflect.Field;import java.lang.reflect.Method;impo......

laolin23
36分钟前
2
0
WordPress没有上级目录的写权限

sudo chmod -R 777 wordpress/wp-content

临江仙卜算子
43分钟前
5
0
大数据学习之大数据技术笔记—spring入门

篇一 spring介绍 spring.io 官网 快速开始 Aop 面向切面编程,可以任何位置,并且可以细致到方法上 连接框架与框架 Spring 就是 IOC AOP 思想 有效的组织中间层对象一般都是切入 service 层 ...

董黎明
44分钟前
6
0
ASP.NET Core MVC 静态文件配置

在启动文件中添加以下配置 public class Startup{ public IServiceProvider ConfigureServices(IServiceCollection services) { services.AddDirectoryBrowser(); ......

whltian
今天
2
0
linux之自定义命令

本人使用的是ubuntu系统,不喜欢建各种桌面快捷链接,但是每次启动个软件,去查找又麻烦,所以自定义了命令,来快捷的启动应用: 1、修改/etc/bash.bashrc,在文件末尾,加上如下List-1中的内...

克虏伯
今天
8
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部