当前位置:首页 > 开发 > 编程语言 > Java > 正文

java-75-二叉树两结点的最低共同父结点

发表于: 2012-02-27   作者:bylijinnan   来源:转载   浏览:
摘要: import java.util.LinkedList; import java.util.List; import ljn.help.*; public class BTreeLowestParentOfTwoNodes { public static void main(String[] args) { /* * node data is stored in
import java.util.LinkedList;
import java.util.List;

import ljn.help.*;
public class BTreeLowestParentOfTwoNodes {

	public static void main(String[] args) {
		/*
		 * node data is stored in leverOrder.'0' represents null node.
		 * e.g.
		 * int[] data={1,8,7,9,2,0,0,0,0,4,7};
		 * the tree is:
		 *           1                                                     
	               /   \                                                    
	               8    7                                                   
	            /    \
	           9     2
	                /  \
	               4    7
		 */
		 int[] data={1,8,7,9,2,0,0,0,0,4,7};
		 Node head=Helper.createTree(data);
		 Node node1=new Node(4);
		 Node node2=new Node(9);//their lowest parent should be 8
		 LinkedList<Node> path1=new LinkedList<Node>();//should be 1,8,2,4
		 LinkedList<Node> path2=new LinkedList<Node>();//should be 1,8,9
		 createPath(head,node1,path1);
		 createPath(head,node2,path2);
		 Node lowestParent=lastCommonNode(path1,path2);
		 System.out.println(lowestParent.getData());
	}

	//create a path from BTree's root to the specific node
	public static boolean createPath(Node head,Node node,LinkedList<Node> path){
		if(head.getData()==node.getData()){
			return true;
		}
		boolean found=false;
		path.addLast(head);
		if(head.getLeft()!=null){
			found=createPath(head.getLeft(),node,path);
		}
		if(!found&&head.getRight()!=null){
			found=createPath(head.getRight(),node,path);
		}
		if(!found){
			path.removeLast();
		}
		return found;
	}
	/*
	 * find 'lastCommonNode' of two list and return.
	 * e.g 
	 * list1=1,2,3,5
	 * list2=1,2,3,4
	 * we return 3
	 */
	public static Node lastCommonNode(List<Node> list1,List<Node> list2){
		Node result=null;
		int len1=list1.size();
		int len2=list2.size();
		if(len1==0||len2==0){
			return null;
		}
		for(int i=0,j=0;i<len1&&j<len2;i++,j++){
			if(list1.get(i)==list2.get(j)){
				result=list1.get(i);
			}
		}
		return result;
	}
}

java-75-二叉树两结点的最低共同父结点

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
题目:二叉树的结点的定义如下: struct TreeNode { int m_nValue; TreeNode *m_pLeft; TreeNode *m
与该题的一道相似题为:求二叉树中结点的最长距离。两题看似有联系,但是做法不同。 首先回顾一下:
题目要求:   输入二叉树中的两个结点,输出这两个及诶单在数中最低的共同父结点。 题目分析:  
之前看到的一道题目。想了一下,借助队列用层次遍历。过程 1、把根结点入队列 2、如果队列非空,重
二叉树的下一个结点 参与人数:831时间限制:1秒空间限制:32768K 通过比例:26.00% 最佳记录:0 ms
// 输出二叉树中所有从根结点到叶子结点的路径.cpp : 定义控制台应用程序的入口点。 #include "stda
做一个带有分支的流向流程 在执行seperate状态的时候分成了200和400两种情况 描述文件的内容如下:
终结点的地址的Uri属性作为终结点地址的唯一标示。 包括客户端终结点和服务端终结点。 一、服务端终
实现二叉查找数root中两个节点的最近相连的双亲节点 以下是递归算法 1、当不含有p,q的路径汇总时,返
java.lang.Object类是所有Java类的最高层次父类,该类中没有定义任何属性,方法也只有几个,但正是这
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号