文档章节

*【九度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
海淀
程序员
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
【九度OJ1521】|【剑指offer19】二叉树的镜像

题目描述: 输入一个二叉树,输出其镜像。 输入: 输入可能包含多个测试样例,输入以EOF结束。 对于每个测试案例,输入的第一行为一个整数n(0<=n<=1000,n代表将要输入的二叉树节点的个数(节...

aqia358
2013/12/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

java大数据转换16进制转10进制

public static void main(String[] args) {String hex = "0xdbf3accc683297cf0000";BigInteger amount = new BigInteger(hex.substring(2), 16);System.out.println(amount);......

任梁荣
昨天
1
0
OSChina 周六乱弹 —— 目测我们程序员丁克的几率不大

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @真Skr小机灵鬼儿:8.13分享Jocelyn Pook/Russian Red的单曲《Loving Strangers》 《Loving Strangers》- Jocelyn Pook/Russian Red 手机党少...

小小编辑
昨天
9
3
TypeScript基础入门 - 函数 - 剩余参数

转载 TypeScript基础入门 - 函数 - 剩余参数 项目实践仓库 https://github.com/durban89/typescript_demo.gittag: 1.2.1 为了保证后面的学习演示需要安装下ts-node,这样后面的每个操作都能...

durban
昨天
1
0
OpenCV边缘检测算子原理总结及实现

1. 拉普拉斯算子 原理:是一种基于图像导数运算的高通线性滤波器。它通过二阶导数来度量图像函数的曲率。 拉普拉斯算子是最简单的各向同性微分算子,它具有旋转不变性。一个二维图像函数的拉...

漫步当下
昨天
0
0
Spring源码阅读——1

开始读Spring源码吧,看再多的技术博客,不如自己看一下~~~~~ Spring源码目前在github中,新版本基于gradle构建。所以阅读源码需要先安装github和gradle。 spring中git地址 1、安装git(略)...

叶枫啦啦
昨天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部