`
standalone
  • 浏览: 606467 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

Find all paths with sum as a given value in a binary three

阅读更多
Problem:
microsoft-interview-questions 57 Answers

Given a value and a binary search tree.
Print all the paths(if there exists more than one) which sum up to that value. It can be any path in the tree. It doesn't have to be from the root.

My code:
I also pasted my code at http://www.careercup.com/question?id=2971

import java.util.Stack;

public class BinarySearchTree {

	private class Node {
		int data;
		Node left;
		Node right;
		Node(int v, Node left, Node right){
			data = v;
			this.left = left;
			this.right = right;
		}		
	}

	public Node root;

	public void insertNode(int data) {
		if (root == null) {
			root = new Node(data, null, null);			
			return;
		}
		Node cur = root;
		do {
			if(data >= cur.data) {
				if(cur.right != null) cur = cur.right;
				else {
					cur.right = new Node(data, null, null);
					return;
				}
			}else {
				if(cur.left != null) cur = cur.left;
				else {
					cur.left = new Node(data, null, null);
					return;
				}
			}
		}while(cur != null);
	}

	public void inorder() {
		System.out.println("\nin-order :");
		printSubTreeInOrder(root);
	}
	
	public void preorder() {
		System.out.println("\npre-order :");
		printSubTreePreOrder(root);
	}
	
	private void printSubTreeInOrder(Node p){
		if(p.left != null) printSubTreeInOrder(p.left);
		System.out.print("\t" + p.data);
		if(p.right != null) printSubTreeInOrder(p.right);
	}
	private void printSubTreePreOrder(Node p){
		System.out.print("\t" + p.data);
		if(p.left != null) printSubTreePreOrder(p.left);		
		if(p.right != null) printSubTreePreOrder(p.right);
	}
	public void printAllPathWithSum(int sum){
		Stack<Node> path = new Stack<Node>();
		findPath(root, sum, path);
	}
	
	private void printPath(Stack<Node> path){
		System.out.print("\nFind Path:");
		for(Node n: path){
			System.out.print("\t" + n.data);
		}
	}
	
	private void findPath(Node p, int value, Stack<Node> path){
		if(p == null) return;
		if(p.data == value){
			path.push(p);
			printPath(path);
			path.pop();
		}else {
			path.push(p);
			if(p.left != null) findPath(p.left, value - p.data, path);
			if(p.right != null)findPath(p.right, value- p.data, path);
			path.pop();			
		}
		if(p.left != null) findPath(p.left, value , path);
		if(p.right != null)findPath(p.right, value, path);
	}

	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

		BinarySearchTree tree = new BinarySearchTree();
		tree.insertNode(5);
		tree.insertNode(2);
		tree.insertNode(7);
		tree.insertNode(1);
		tree.insertNode(3);
		tree.insertNode(9);
		tree.inorder();
		tree.preorder();
		tree.printAllPathWithSum(1);
		tree.printAllPathWithSum(0);
		tree.printAllPathWithSum(16);
		tree.printAllPathWithSum(9);
	}

}

分享到:
评论

相关推荐

    Profiling all paths

    A recent study published in *The Journal of Systems and Software* (Volume 85, 2012, Pages 1558–1576) introduces a new profiling technique called "Profiling All Paths" (PAP). This approach aims to ...

    算法上机!!

     A multistage graph is a graph (1) G=(V,E) with V partitioned into K &gt;= 2 disjoint subsets such that if (a,b) is in E, then a is in Vi , and b is in Vi+1 for some subsets in the partition; and (2) | ...

    A Course on Rough Paths

    As a consequence, there are a number of aspects that we chose not to touch, or to do so only barely. One omission is the study of rough paths of arbitrarily low regularity: we do provide hints at the ...

    LeetCode — Path Sum III分析及实现方法

    Find the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes

    servlet2.4doc

    Adds a response header with the given name and value. addIntHeader(String, int) - Method in class javax.servlet.http.HttpServletResponseWrapper The default behavior of this method is to call ...

    计算机网络第六版答案

    27. Creation of a botnet requires an attacker to find vulnerability in some application or system (e.g. exploiting the buffer overflow vulnerability that might exist in an application). After finding ...

    TMS Pack for FireMonkey2.3.0.1

    Fixed : Issue with scrolling and selecting value in iOS in TTMSFMXSpinner Fixed : Issue with escape key not cancelling edit mode in TTMSFMXGrid v1.6.0.1 Fixed : Issue with double databinding ...

    A Novel High-Voltage Pseudo-p-LDMOS Device With Three Current Conductive Paths

    A new concept high-voltage pseudo-pchannel lateral double-diffused MOS (p-LDMOS) with multiple current paths for conduction is proposed and investigated in this paper. The proposed power device ...

    java-leetcode题解之 All Paths From Source to Target.java

    java基础 java_leetcode题解之 All Paths From Source to Target.java

    Access Path Selection in a Relational Database Management System

    In a high level query and data manipulation language such as SQL, requests are stated non-procedurally, without reference to access paths. This paper describes how System R chooses access paths for ...

    Google C++ Style Guide(Google C++编程规范)高清PDF

    All of a project's header files should be listed as descentants of the project's source directory without use of UNIX directory shortcuts . (the current directory) or .. (the parent directory). For...

    基于dijkstra的低耗路由matlab仿真

    NOTE: only valid with A as the first input C is a NxN cost (perhaps distance) matrix, where C(I,J) contains the value of the cost to move from point I to point J NOTE: only valid with A as the ...

    Geometric Modeling in Shape Space【pdf】

    - The authors introduce the concept of treating shapes (triangular meshes or more generally straight-line graphs in Euclidean space) as points in a shape space. - This approach enables the ...

    【视频教程】Hands-on Three.js 3D Web Visualisations-September 16, 2019.part1.rar-共三分卷

    This course begins with a 3D beginner-level primer to 3D concepts and some basic examples to get you started with the most important features that Three.js has to offer. You’ll learn how to quickly ...

    ehlib_vcl_src_9_3.26

    with a scrollable list and can display and edit a field in a dataset or can works as non data-aware combo edit control. TDBNumberEditEh component represents a single-line number edit control that ...

    ios openssl静态库 (libssl.a和libcrypto.a) 基于最新的1.0.2m

    完成这一步后,将`universal`目录下的`libssl.a`和`libcrypto.a`添加到Xcode项目的`Link Binary With Libraries`阶段,并确保它们被包含在项目的`Copy Files`构建阶段,以便在应用包中包含这些静态库。 接下来,...

    Hands-on Three.js 3D Web Visualisations-September 16, 2019.part2.rar-共三分卷

    This course begins with a 3D beginner-level primer to 3D concepts and some basic examples to get you started with the most important features that Three.js has to offer. You’ll learn how to quickly ...

    EhLib 9.1.024

    with a scrollable list and can display and edit a field in a dataset or can works as non data-aware combo edit control. TDBNumberEditEh component represents a single-line number edit control that ...

    CE中文版-启点CE过NP中文.exe

    Added an option to filter out readable paths in the pointerscan rescan Added "codePage" support Added font/display options to several places in CE Added a search/replace to the script editors You can ...

Global site tag (gtag.js) - Google Analytics