在二元树中找出和为某一值的所有路径

题目：

 

题目：输入一个整数和一棵二元树。
从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。
打印出和与输入整数相等的所有路径。
例如 输入整数22和如下二元树
  10  
  / \  
  5 12  
  / \  
  4 7

则打印出两条路径：10, 12和10, 5, 7。

思路：有两种方法，递归和非递归。其中非递归使用前序遍历，一条路走到底，并且每次访问一个节点，就判断当前访问的节点是否符合要求，符合就进栈保持，不然就退栈，对退出来的节点判断是否有右子树，有就继续往下，否则就继续退栈。

代码：

 

递归：

public void findPath(BiSearchTree node,int sum, String path){
		sum  = sum - node.data;
		if(sum<0){
			return;
		}else if(sum==0){
			path = path + " " + node.data;
			System.out.println("Path: "+path);
		}else{
			if(node.LeftTree!=null){
				findPath(node.LeftTree, sum , path + " " + node.data);
			}
			if(node.RightTree!=null){
				findPath(node.RightTree, sum,path + " " + node.data);
			}
		}
		
	}
	

 

 

非递归：

 

public void findPath(BiSearchTree node,int sum){
		BiSearchTree pre = null;
		Stack stack = new Stack();
		do{
			while(node!=null){
				
				sum = sum - node.data;
				if(sum<0){
					break;
				}else if(sum==0){
					pre = node;
					sum = sum + node.data;
					System.out.println("I find "+node.data);
				}else{
					stack.push(node);
				}
				if(node.LeftTree!=null)
					pre = node;
				node = node.LeftTree;
			}
			node = (BiSearchTree)stack.pop();
			if(node.RightTree==null||node.RightTree==pre){
				pre = node;
				sum = sum + node.data;
				node = null;
			}else {
				stack.push(node);
				pre = node;
				node = node.RightTree;
			}
		}while(!stack.IsEmpty());
	}

 

非递归打印出来的只是符合要求的最后一个节点。

可以打印出栈的全部元素。

 

评论

2 楼 kingj 2014-04-10  

将if(node.RightTree==null||node.RightTree==pre)
改为if(node.RightTree==null || node.RightTree==pre || node.LeftTree!=pre)

1 楼 kingj 2014-04-10  

非递归的算法在下面这种情况下会有问题
                          10
/   \
5     12
       /  \    /
      4    7  0
          node = (BiSearchTree)stack.pop(); 
            if(node.RightTree==null||node.RightTree==pre){ 
                pre = node; 
                sum = sum + node.data; 
                node = null; 
            }else { 
                stack.push(node); 
                pre = node; 
                node = node.RightTree; 
            } 
会导致在遇到0的时候无限循环