0820-mirosoft

传说中微软的几道算法题，练习一下吧：

 

1.设计一个算法，找出二叉树上任意两个结点的最近共同父结点。
复杂度如果是O(n2)则不得分。

 

	/*
	 * 获得两个节点共同的父节点
	 */
	public ArrayList<BiTreeNode> getCommonParents(BiTreeNode node1,
			BiTreeNode node2, BiTreeNode root) {
		ArrayList<BiTreeNode> commonList = new ArrayList<BiTreeNode>();
		ArrayList<BiTreeNode> node1ParentList = new ArrayList<BiTreeNode>();
		ArrayList<BiTreeNode> node2ParentList = new ArrayList<BiTreeNode>();
		node1ParentList = getParents(node1, root);
		node2ParentList = getParents(node2, root);
		int len1 = node1ParentList.size();
		int len2 = node2ParentList.size();
		for (int i = 0; (i < len1) && (i < len2); i++) {
			char data1 = node1ParentList.get(i).getData();
			char data2 = node2ParentList.get(i).getData();
			if (data1 == data2) {
				commonList.add(node1ParentList.get(i));
			}
		}

		return commonList;

	}

	/*
	 * 获得一个节点的所有父节点
	 */
	ArrayList<BiTreeNode> getParents(BiTreeNode node, BiTreeNode root) {
		int top = 0;
		ArrayList<BiTreeNode> stack = new ArrayList<BiTreeNode>();
		BiTreeNode pointer = root;
		while (top > 0 || pointer != null) {
			if (pointer != null) {
				if (pointer.getData() == node.getData()) {
					return stack;
				}
				stack.add(pointer);
				top++;
				pointer = pointer.getLeftChild();
			} else {
				BiTreeNode topNode = stack.get(top - 1);
				while(topNode.getVisit() == 1) {
					stack.remove(--top);
					topNode = stack.get(top - 1);
				} 
				topNode.setVisit(1);
				pointer = topNode.getRightChild();
			}
		}

		return stack;
	}

 

   

 

2.一棵排序二叉树，令 f=(最大值+最小值)/2，设计一个算法，找出距离f值最近、大于f值的结点。
复杂度如果是O(n2)则不得分。

 

package org.jyjiao;
import java.util.*;
//创建一棵二叉树
//判定是否是一棵二叉排序树
//插入一个节点
//一棵排序二叉树，令 f=(最大值+最小值)/2，设计一个算法，找出距离f值最近、大于f值的结点。复杂度如果是O(n2)则不得分。
/*已知有一棵二叉排序树，其中保存了 n 个互不相同的元素，且左子树中的元素小于根小于右子树中的元素。现在给你这棵二叉排序树的前序遍历序列，请你给出一个算法能够把这棵二叉排序树重新构造起来。具体实现不拘，用伪码说明也可以，但是要求： 

1、说明你的算法的正确性。 
2、分析你的算法的时间复杂度。
*/

class TreeNode{
	int data;
	TreeNode leftChild,rightChild;
	public int getData(){
		return this.data;
	}
	public void setData(int data){
		this.data=data;
	}
	
	public TreeNode getLeftChild(){
		return this.leftChild;
	}
	public TreeNode getRightChild(){
		return this.rightChild;
	}
	
	public void setLeftChild(TreeNode leftChild){
		this.leftChild=leftChild;
	}
	public void setRightChild(TreeNode rightChild){
		this.rightChild=rightChild;
	}
	
	public TreeNode(int data){
		this.data=data;
		this.leftChild=null;
		this.rightChild=null;
	}
		
}

public class OrderBiTree{
	TreeNode root;
	ArrayList<TreeNode> nodeArray=new ArrayList<TreeNode>();

	public OrderBiTree(){
		root=null;
	}
	public TreeNode createOrderTree(int[] array){
		for(int i=0;i<array.length;i++){
			TreeNode newNode=new TreeNode(array[i]);
			insert(newNode);
		}
		return root;
	}
	
	public void insert(TreeNode node){
		if(root==null){
			root=node;
		}
		else{
			TreeNode pNode=root;
			while(true){
				if(node.getData()<=pNode.getData()){
					if(pNode.getLeftChild()==null){
						pNode.setLeftChild(node);
						return;
					}else{
						pNode=pNode.getLeftChild();
					}
				}
				else{
					if(pNode.getRightChild()==null){
						pNode.setRightChild(node);
						return;
					}else{
						pNode=pNode.getRightChild();
					}
					
				}
			}//while
		}//else
	}
	
	public TreeNode findNode(TreeNode root){
		if(root==null){
			return null;
		}
		int middle=(nodeArray.get(0).getData()+nodeArray.get(nodeArray.size()-1).getData())/2;
		TreeNode pointer=root;
		ArrayList<TreeNode> bigList=new ArrayList<TreeNode>(); 
		
		while(true){
			if(middle<=pointer.getData()){
				bigList.add(pointer);
				if(pointer.getLeftChild()==null){
					break;
				}
				pointer=pointer.getLeftChild();
			}
			if(middle>pointer.getData()){
				if(pointer.getRightChild()==null){
					break;
				}
				pointer=pointer.getRightChild();
			}
		}
		return bigList.get(bigList.size()-1);
		
		
	}
	
	
	public void middleTravel(TreeNode root){
		if(root==null){
			return;
		}
		middleTravel(root.getLeftChild());
		System.out.print(root.getData()+" ");
		nodeArray.add(root);
		middleTravel(root.getRightChild());
		
	}
	
	public static void main(String[] args){
		int[] array={10,9,3,15,20,5,30};
		OrderBiTree tree=new OrderBiTree();
		TreeNode orderTree=tree.createOrderTree(array);
		tree.middleTravel(orderTree);
		TreeNode bigNode=tree.findNode(orderTree);
		System.out.println("\nbigNode.getData()="+bigNode.getData());
	}
	
}

 

3.一个整数数列，元素取值可能是1~N（N是一个较大的正整数）中的任意一个数，相同数值不会重复出现。设计一个算法，找出数列中符合条件的数对的个数，满足数对中两数的和等于N+1。
复杂度最好是O(n)，如果是O(n2)则不得分。