微軟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);
  }

}