微软100题-天天做-第四题

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

题目：输入一个整数和一棵二元树。

从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。

打印出和与输入整数相等的所有路径。

例如 输入整数22和如下二元树

10  
   /   /   
  5    12   
 / \     
 4  7      

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

二元树节点的数据结构定义为：

struct BinaryTreeNode // a node in the binary tree
 {
 int m_nValue; // value of node
 BinaryTreeNode *m_pLeft; // left child of node
 BinaryTreeNode *m_pRight; // right child of node
 }      

;

package com.microsoft;

import java.util.Random;

public class ValuePathTree {
  private Node root;

  public ValuePathTree(int[] data) {
    for (int i = 0; i < data.length; i++) {
      Node node = new Node();
      node.value = data[i];
      node.leaf = true;
      insert(node);
    }
  }

  public void insert(Node node) {
    insert(root, node, true);
  }

  public void insert(Node parent, Node node, boolean left) {
    if (parent != root && parent.leaf && left) {
      parent.leaf = false;
      parent.left = node;
      node.parent = parent;
      int weight = node.value;
      Node p = node.parent;
      node.weight = weight + p.weight;
      return;
    } else if (parent != root && parent.leaf && !left) {
      parent.leaf = false;
      parent.right = node;
      node.parent = parent;
      int weight = node.value;
      Node p = node.parent;
      node.weight = weight + p.weight;
      return;
    }
    if (parent == null) {
      root = node;
      node.weight = node.value;
      return;
    }
    int random = new Random().nextInt(2);
    if (random == 1) {
      if (parent.left == null) {
        parent.left = node;
        parent.leaf = false;
        node.parent = parent;
        int weight = node.value;
        Node p = node.parent;
        node.weight = weight + p.weight;
      } else {
        insert(parent.left, node, true);
      }

    } else {
      if (parent.right == null) {
        parent.right = node;
        parent.leaf = false;
        node.parent = parent;
        int weight = node.value;
        Node p = node.parent;
        node.weight = weight + p.weight;
      } else {
        insert(parent.right, node, false);
      }

    }
  }

  public void print() {
    Node h = this.root;
    this.print(0, h);
  }

  private void print(int level, Node node) {
    for (int i = 0; i < level; i++) {
      System.out.format(" ");
    }
    System.out.format("|");
    for (int i = 0; i < level; i++) {
      System.out.format("-");
    }

    System.out.format("%d,%s%n", node.value, node.weight);
    Node left = node.left;
    Node right = node.right;
    if (left != null) {
      print(level + 1, left);
    }
    if (right != null) {
      print(level + 1, right);
    }
  }

  private class Node {
    private Node parent;
    private Node left;
    private Node right;
    private boolean leaf;
    private int value;
    private int weight;
  }
  
  public void printPath(int weight){
    printPath(root,weight);
  }
  
  public void printPath(Node node,int weight){
    if(node==null){
      return;
    }
    if(!node.leaf){
      if(node.weight>weight){
        return;
      }else{
        printPath(node.left,weight);
        printPath(node.right,weight);
      }
    }else{
      if(node.weight==weight){
        StringBuffer sb=new StringBuffer();
        Node n=node;
        while(n!=null){
          sb.append(n.value+"-");
          n=n.parent;
        }
        sb.reverse();
        System.out.println(sb.toString());
        return;
      }else{
        return;
      }
    }
  }

  public static void main(String[] args) {
    int[] data = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,1,2,3,4,5,6,7 };
    ValuePathTree tree = new ValuePathTree(data);
    tree.print();
    tree.printPath(14);
  }

}