本文共 3598 字，大约阅读时间需要 11 分钟。

Java与算法（12）

1.二叉树节点间最大距离问题

给定头节点，求最大距离

public class MaxDIstance {	public static class Node {		public int value;		public Node left;		public Node right;		public Node(int data) {			this.value = data;		}	}	public static int maxDistance(Node head) {		int[] record = new int[1];		return posOrder(head, record);	}	public static int posOrder(Node head, int[] record) {		if (head == null) {			record[0] = 0;			return 0;		}		int lMax = posOrder(head.left, record);		int maxfromLeft = record[0];		int rMax = posOrder(head.right, record);		int maxFromRight = record[0];		int curNodeMax = maxfromLeft + maxFromRight + 1;		record[0] = Math.max(maxfromLeft, maxFromRight) + 1;		return Math.max(Math.max(lMax, rMax), curNodeMax);	}	public static void main(String[] args) {		Node head1 = new Node(1);		head1.left = new Node(2);		head1.right = new Node(3);		head1.left.left = new Node(4);		head1.left.right = new Node(5);		head1.right.left = new Node(6);		head1.right.right = new Node(7);		head1.left.left.left = new Node(8);		head1.right.left.right = new Node(9);		System.out.println(maxDistance(head1));	}}

2.找出两个节点的最近公共祖先

public class LowAncestor {	public static class Node {		public int value;		public Node left;		public Node right;		public Node(int data) {			this.value = data;		}	}		public static Node lowestAncestor(Node head, Node o1, Node o2) {		if (head == null || head == o1 || head == o2) {			return head;		}		Node left = lowestAncestor(head.left, o1, o2);		Node right = lowestAncestor(head.right, o1, o2);		if (left != null && right != null) {			return head;		}		return left != null ? left : right;	}	public static void main(String[] args) {		Node head = new Node(1);		head.left = new Node(2);		head.right = new Node(3);		head.left.left = new Node(4);		head.left.right = new Node(5);		head.right.left = new Node(6);		head.right.right = new Node(7);		head.right.right.left = new Node(8);		Node o1 = head.left.right;		Node o2 = head.right.left;				System.out.println("o1 : " + o1.value);		System.out.println("o2 : " + o2.value);		System.out.println("ancestor : " + lowestAncestor(head, o1, o2).value);							}}

3.在二叉树找到一个节点的后继节点

public class GetNextNode {	public static class Node {		public int value;		public Node left;		public Node right;		public Node parent;		public Node(int data) {			this.value = data;		}	}	public static Node getNextNode(Node node) {		if (node == null) {			return node;		}		if (node.right != null) {			return getLeftMost(node.right);		} else {			Node parent = node.parent;			while (parent != null && parent.left != node) {				node = parent;				parent = node.parent;			}			return parent;		}	}	public static Node getLeftMost(Node node) {		if (node == null) {			return node;		}		while (node.left != null) {			node = node.left;		}		return node;	}				public static void main(String[] args) {		Node head = new Node(6);		head.parent = null;		head.left = new Node(3);		head.left.parent = head;		head.left.left = new Node(1);		head.left.left.parent = head.left;		head.left.left.right = new Node(2);		head.left.left.right.parent = head.left.left;		head.left.right = new Node(4);		head.left.right.parent = head.left;		head.left.right.right = new Node(5);		head.left.right.right.parent = head.left.right;		head.right = new Node(9);		head.right.parent = head;		head.right.left = new Node(8);		head.right.left.parent = head.right;		head.right.left.left = new Node(7);		head.right.left.left.parent = head.right.left;		head.right.right = new Node(10);		head.right.right.parent = head.right;		Node test = head.left.right.right;		Node node = getNextNode(test);		System.out.println(node.value);					}}

转载地址：http://svcqb.baihongyu.com/