算法之乐：一个算法解决3道经典二叉树面试题（深度、长度、直径）

时间：2022-09-26 14:19:14

有了昨天《Java实现二叉树的构建以及3种遍历方法》的二叉树数据结构基础，今天我们通过一个算法解决3道关于二叉树的经典面试题（深度、长度、直径），触类旁通，举一反三，尽享算法之乐。

测试二叉树：

算法之乐：一个算法解决3道经典二叉树面试题（深度、长度、直径）

例题：给定一个二叉树，计算它的最大深度。深度是指根节点到子节点路径中的节点个数。

如图，1->8/9的深度为4（1-2-4-8/9），这也是这棵二叉树的最大深度。

我们定义一个Result类，里面包含一个整型变量nMaxDepth，并重写它的toString方法。

	private static class Result  
	{  
	    int nMaxDepth;//深度，根节点到子节点路径中的节点个数。
	    
	    @Override
	    public String toString() {
	    	return "nMaxDepth:" + nMaxDepth;
	    }
	};


我们梳理一下算法，一棵二叉树的最大深度等于1+ Max(左子树的最大深度, 右子树的最大深度)，用递归的思想，左子树的最大深度等于以左子树首节点为根节点，再求1+ Max(左左子树的最大深度, 左右子树的最大深度)，直到节点为空，nMaxDepth=0。

result.nMaxDepth = 1+ Math.max(leftResult.nMaxDepth, rightResult.nMaxDepth);


结合实例：从根节点1开始，先求他左子树的最大深度，来到2，继续求它左子树的最大深度，···，1-2-4-8，

此时对于8，1+ Max(左子树的最大深度, 右子树的最大深度)=1+（0,0）=1：

root.leftChild:null
leftResult:nMaxDepth:0
root.rightChild:null
rightResult:nMaxDepth:0
root.leftChild:data:8,leftChild:null,rightChild:null

leftResult:nMaxDepth:1
然后退到4，求它右子树的最大深度，进到9，1+ Max(左子树的最大深度, 右子树的最大深度)=1+（0,0）=1：

root.leftChild:null
leftResult:nMaxDepth:0
root.rightChild:null
rightResult:nMaxDepth:0
root.rightChild:data:9,leftChild:null,rightChild:null
rightResult:nMaxDepth:1

回到4=1+ Max(左子树的最大深度, 右子树的最大深度)=1+（1,1）=2：

root.leftChild:data:4,leftChild:data:8,leftChild:null,rightChild:null,rightChild:data:9,leftChild:null,rightChild:null
leftResult:nMaxDepth:2

回到2，进到5=1+ Max(左子树的最大深度, 右子树的最大深度)=1+（0,0）=1：

root.leftChild:null
leftResult:nMaxDepth:0
root.rightChild:null
rightResult:nMaxDepth:0
root.rightChild:data:5,leftChild:null,rightChild:null
rightResult:nMaxDepth:1

退回到2=1+ Max(左子树的最大深度, 右子树的最大深度)=1+（2,1）=3：

root.leftChild:data:2,leftChild:data:4,leftChild:data:8,leftChild:null,rightChild:null,rightChild:data:9,leftChild:null,rightChild:null,rightChild:data:5,leftChild:null,rightChild:null
leftResult:nMaxDepth:3

同理求1的右子树，1-3-6（1）-7（1）-3（2）-1（4）。

我们看一下算法的Java实现：

	public static Result compDiameter(Node root) {
		if (root == null) {
			Result empty = new Result();
			empty.nMaxDepth = 0;
			return empty;
		}
		Result leftResult = compDiameter(root.leftChild);
		System.out.println("root.leftChild:" + root.leftChild);
		System.out.println("leftResult:" + leftResult);
		Result rightResult = compDiameter(root.rightChild);
		System.out.println("root.rightChild:" + root.rightChild);
		System.out.println("rightResult:" + rightResult);
		Result result = new Result();
		result.nMaxDepth = 1+ Math.max(leftResult.nMaxDepth, rightResult.nMaxDepth);  
		return result;
	}


结合输出结果在理解一下算法的过程：

root.leftChild:null
leftResult:nMaxDepth:0
root.rightChild:null
rightResult:nMaxDepth:0
root.leftChild:data:8,leftChild:null,rightChild:null
leftResult:nMaxDepth:1
root.leftChild:null
leftResult:nMaxDepth:0
root.rightChild:null
rightResult:nMaxDepth:0
root.rightChild:data:9,leftChild:null,rightChild:null
rightResult:nMaxDepth:1
root.leftChild:data:4,leftChild:data:8,leftChild:null,rightChild:null,rightChild:data:9,leftChild:null,rightChild:null
leftResult:nMaxDepth:2
root.leftChild:null
leftResult:nMaxDepth:0
root.rightChild:null
rightResult:nMaxDepth:0
root.rightChild:data:5,leftChild:null,rightChild:null
rightResult:nMaxDepth:1
root.leftChild:data:2,leftChild:data:4,leftChild:data:8,leftChild:null,rightChild:null,rightChild:data:9,leftChild:null,rightChild:null,rightChild:data:5,leftChild:null,rightChild:null
leftResult:nMaxDepth:3
root.leftChild:null
leftResult:nMaxDepth:0
root.rightChild:null
rightResult:nMaxDepth:0
root.leftChild:data:6,leftChild:null,rightChild:null
leftResult:nMaxDepth:1
root.leftChild:null
leftResult:nMaxDepth:0
root.rightChild:null
rightResult:nMaxDepth:0
root.rightChild:data:7,leftChild:null,rightChild:null
rightResult:nMaxDepth:1
root.rightChild:data:3,leftChild:data:6,leftChild:null,rightChild:null,rightChild:data:7,leftChild:null,rightChild:null
rightResult:nMaxDepth:2
计算结果：nMaxDepth:4

稍微回味一下，我们举一反二：

变体：给定一个二叉树，计算它的最大长度。长度是指二叉树两个节点之间的路径中边的个数。

如图，最大长度为8/9-6/7=5，

结合例题的基础分析，最大长度=左子树最大深度+右子树最大深度，5=3+2。

result.nMaxDistance = leftResult.nMaxDepth + rightResult.nMaxDepth

我们在Result类中追加长度变量nMaxDistance，并重写toString方法。

	private static class Result  
	{  
	    int nMaxDepth;//深度,根节点到子节点路径中的节点个数。
	    int nMaxDistance;//长度,二叉树两个节点之间的路径中边的个数。

	    @Override
	    public String toString() {
	    	return "nMaxDepth:" + nMaxDepth + ",nMaxDistance:" + nMaxDistance;
	    }
	};


在核心算法中添加2行代码：

1.当根节点为空时，empty.nMaxDistance = 0;

2.长度计算：result.nMaxDistance = leftResult.nMaxDepth + rightResult.nMaxDepth;

	public static Result compDiameter(Node root) {
		if (root == null) {
			Result empty = new Result();
			empty.nMaxDepth = 0;
			empty.nMaxDistance = 0;
			return empty;
		}
		Result leftResult = compDiameter(root.leftChild);
		System.out.println("root.leftChild:" + root.leftChild);
		System.out.println("leftResult:" + leftResult);
		Result rightResult = compDiameter(root.rightChild);
		System.out.println("root.rightChild:" + root.rightChild);
		System.out.println("rightResult:" + rightResult);
		Result result = new Result();
		result.nMaxDepth = 1+ Math.max(leftResult.nMaxDepth, rightResult.nMaxDepth);  
        	result.nMaxDistance = leftResult.nMaxDepth + rightResult.nMaxDepth;
		return result;
	}

过程类似，输出结果：

root.leftChild:null
leftResult:nMaxDepth:0,nMaxDistance:0
root.rightChild:null
rightResult:nMaxDepth:0,nMaxDistance:0
root.leftChild:data:8,leftChild:null,rightChild:null
leftResult:nMaxDepth:1,nMaxDistance:0
root.leftChild:null
leftResult:nMaxDepth:0,nMaxDistance:0
root.rightChild:null
rightResult:nMaxDepth:0,nMaxDistance:0
root.rightChild:data:9,leftChild:null,rightChild:null
rightResult:nMaxDepth:1,nMaxDistance:0
root.leftChild:data:4,leftChild:data:8,leftChild:null,rightChild:null,rightChild:data:9,leftChild:null,rightChild:null
leftResult:nMaxDepth:2,nMaxDistance:2
root.leftChild:null
leftResult:nMaxDepth:0,nMaxDistance:0
root.rightChild:null
rightResult:nMaxDepth:0,nMaxDistance:0
root.rightChild:data:5,leftChild:null,rightChild:null
rightResult:nMaxDepth:1,nMaxDistance:0
root.leftChild:data:2,leftChild:data:4,leftChild:data:8,leftChild:null,rightChild:null,rightChild:data:9,leftChild:null,rightChild:null,rightChild:data:5,leftChild:null,rightChild:null
leftResult:nMaxDepth:3,nMaxDistance:3
root.leftChild:null
leftResult:nMaxDepth:0,nMaxDistance:0
root.rightChild:null
rightResult:nMaxDepth:0,nMaxDistance:0
root.leftChild:data:6,leftChild:null,rightChild:null
leftResult:nMaxDepth:1,nMaxDistance:0
root.leftChild:null
leftResult:nMaxDepth:0,nMaxDistance:0
root.rightChild:null
rightResult:nMaxDepth:0,nMaxDistance:0
root.rightChild:data:7,leftChild:null,rightChild:null
rightResult:nMaxDepth:1,nMaxDistance:0
root.rightChild:data:3,leftChild:data:6,leftChild:null,rightChild:null,rightChild:data:7,leftChild:null,rightChild:null
rightResult:nMaxDepth:2,nMaxDistance:2
计算结果：nMaxDepth:4,nMaxDistance:5

稍加回味一下，我们举一反三：

变体：给定一个二叉树，计算它的直径。直径是指节点之间最长路径中节点个数。

如图，直径为8/9-6/7=6，


有了之前2道题的基础，直径=根节点（1）+左子树最大深度+右子树最大深度=1+最大长度。

result.nodeNum = 1 + leftResult.nMaxDepth + rightResult.nMaxDepth = 1 + nMaxDistance;


我们追加直径变量nodeNum并重写toString方法：

	private static class Result  
	{  
	    int nMaxDepth;//深度,根节点到子节点路径中的节点个数。
	    int nMaxDistance;//长度,二叉树两个节点之间的路径中边的个数。
	    int nodeNum;//直径,节点之间最长路径中节点个数。
	    
	    @Override
	    public String toString() {
	    	return "nodeNum:" + nodeNum + ",nMaxDistance:" + nMaxDistance + ",nMaxDepth:" + nMaxDepth;
	    }
	};

在核心算法中添加2行代码：

1.当根节点为空时，empty.nodeNum = 0;;

2.直径计算：result.nodeNum = 1 + leftResult.nMaxDepth + rightResult.nMaxDepth;

过程类似，输出结果：

root.leftChild:null
leftResult:nodeNum:0,nMaxDistance:0,nMaxDepth:0
root.rightChild:null
rightResult:nodeNum:0,nMaxDistance:0,nMaxDepth:0
root.leftChild:data:8,leftChild:null,rightChild:null
leftResult:nodeNum:1,nMaxDistance:0,nMaxDepth:1
root.leftChild:null
leftResult:nodeNum:0,nMaxDistance:0,nMaxDepth:0
root.rightChild:null
rightResult:nodeNum:0,nMaxDistance:0,nMaxDepth:0
root.rightChild:data:9,leftChild:null,rightChild:null
rightResult:nodeNum:1,nMaxDistance:0,nMaxDepth:1
root.leftChild:data:4,leftChild:data:8,leftChild:null,rightChild:null,rightChild:data:9,leftChild:null,rightChild:null
leftResult:nodeNum:3,nMaxDistance:2,nMaxDepth:2
root.leftChild:null
leftResult:nodeNum:0,nMaxDistance:0,nMaxDepth:0
root.rightChild:null
rightResult:nodeNum:0,nMaxDistance:0,nMaxDepth:0
root.rightChild:data:5,leftChild:null,rightChild:null
rightResult:nodeNum:1,nMaxDistance:0,nMaxDepth:1
root.leftChild:data:2,leftChild:data:4,leftChild:data:8,leftChild:null,rightChild:null,rightChild:data:9,leftChild:null,rightChild:null,rightChild:data:5,leftChild:null,rightChild:null
leftResult:nodeNum:4,nMaxDistance:3,nMaxDepth:3
root.leftChild:null
leftResult:nodeNum:0,nMaxDistance:0,nMaxDepth:0
root.rightChild:null
rightResult:nodeNum:0,nMaxDistance:0,nMaxDepth:0
root.leftChild:data:6,leftChild:null,rightChild:null
leftResult:nodeNum:1,nMaxDistance:0,nMaxDepth:1
root.leftChild:null
leftResult:nodeNum:0,nMaxDistance:0,nMaxDepth:0
root.rightChild:null
rightResult:nodeNum:0,nMaxDistance:0,nMaxDepth:0
root.rightChild:data:7,leftChild:null,rightChild:null
rightResult:nodeNum:1,nMaxDistance:0,nMaxDepth:1
root.rightChild:data:3,leftChild:data:6,leftChild:null,rightChild:null,rightChild:data:7,leftChild:null,rightChild:null
rightResult:nodeNum:3,nMaxDistance:2,nMaxDepth:2
计算结果：nodeNum:6,nMaxDistance:5,nMaxDepth:4


多思考，举一反三，在算法的海洋里遨游。


最后附上包括建树、遍历等操作的完整源代码，原创不易，转载请注明出处哈。

权兴权意-算法之乐：一个算法解决3道经典二叉树面试题（深度、长度、直径）

http://blog.csdn.net/hxqneuq2012/article/details/52766162


import java.util.LinkedList;
import java.util.List;

public class BinaryTree {

	private int[] array = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	private static List<Node> nodeList = new LinkedList<Node>();;

	private static class Node {
		Node leftChild;
		Node rightChild;
		int data;

		Node(int newData) {
			leftChild = null;
			rightChild = null;
			data = newData;
		}

		@Override
		public String toString() {
			return "data:" + data + ",leftChild:" + leftChild + ",rightChild:"
					+ rightChild;
		}
	}
	
	private static class Result  
	{  
	    int nMaxDepth;//深度,根节点到子节点路径中的节点个数。
	    int nMaxDistance;//长度,二叉树两个节点之间的路径中边的个数。
	    int nodeNum;//直径,节点之间最长路径中节点个数。
	    
	    @Override
	    public String toString() {
	    	return "nodeNum:" + nodeNum + ",nMaxDistance:" + nMaxDistance + ",nMaxDepth:" + nMaxDepth;
	    }
//	    @Override
//	    public String toString() {
//	    	return "nMaxDepth:" + nMaxDepth + ",nMaxDistance:" + nMaxDistance;
//	    }
	}; 

	/*
	 * 给定一个二叉树，计算它的深度、长度、直径。
	 * 深度,根节点到子节点路径中的节点个数。
	 * 长度,二叉树两个节点之间的路径中边的个数。
	 * 直径,节点之间最长路径中节点个数。
	 */
	public static Result compDiameter(Node root) {
		if (root == null) {
			Result empty = new Result();
			empty.nMaxDepth = 0;
			empty.nMaxDistance = 0;
			empty.nodeNum = 0;
			return empty;
		}
		Result leftResult = compDiameter(root.leftChild);
		System.out.println("root.leftChild:" + root.leftChild);
		System.out.println("leftResult:" + leftResult);
		Result rightResult = compDiameter(root.rightChild);
		System.out.println("root.rightChild:" + root.rightChild);
		System.out.println("rightResult:" + rightResult);
		Result result = new Result();
		result.nMaxDepth = 1+ Math.max(leftResult.nMaxDepth, rightResult.nMaxDepth);  
	    result.nMaxDistance = leftResult.nMaxDepth + rightResult.nMaxDepth;
	    result.nodeNum = 1 + leftResult.nMaxDepth + rightResult.nMaxDepth;
		return result;
	}

	public void createBinTree() {
		// 将一个数组的值依次转换为Node节点
		for (int nodeIndex = 0; nodeIndex < array.length; nodeIndex++) {
			nodeList.add(new Node(array[nodeIndex]));
		}
		// 对前lastParentIndex-1个父节点按照父节点与孩子节点的数字关系建立二叉树
		for (int parentIndex = 0; parentIndex < array.length / 2 - 1; parentIndex++) {
			// 左孩子
			nodeList.get(parentIndex).leftChild = nodeList
					.get(parentIndex * 2 + 1);
			// 右孩子
			nodeList.get(parentIndex).rightChild = nodeList
					.get(parentIndex * 2 + 2);
		}
		// 最后一个父节点:因为最后一个父节点可能没有右孩子，所以单独拿出来处理
		int lastParentIndex = array.length / 2 - 1;
		// 左孩子
		nodeList.get(lastParentIndex).leftChild = nodeList
				.get(lastParentIndex * 2 + 1);
		// 右孩子,如果数组的长度为奇数才建立右孩子
		if (array.length % 2 == 1) {
			nodeList.get(lastParentIndex).rightChild = nodeList
					.get(lastParentIndex * 2 + 2);
		}
	}

	/**
	 * 先序遍历
	 */
	public static void preOrderTraverse(Node node) {
		if (node == null)
			return;
		System.out.print(node.data + " ");
		preOrderTraverse(node.leftChild);
		preOrderTraverse(node.rightChild);
	}

	/**
	 * 中序遍历
	 */
	public static void inOrderTraverse(Node node) {
		if (node == null)
			return;
		inOrderTraverse(node.leftChild);
		System.out.print(node.data + " ");
		inOrderTraverse(node.rightChild);
	}

	/**
	 * 后序遍历
	 */
	public static void postOrderTraverse(Node node) {
		if (node == null)
			return;
		postOrderTraverse(node.leftChild);
		postOrderTraverse(node.rightChild);
		System.out.print(node.data + " ");
	}

	/**
	 * 权兴权意-2016.10.8
	 */
	public static void main(String[] args) {
		BinaryTree binTree = new BinaryTree();
		binTree.createBinTree();
		/*
		 * 二叉树： 
		 * 		   1 
		 * 		2     3 
		 *     4  5  6   7 
		 *    8 9
		 */
		// nodeList中第0个索引处的值即为根节点
		Node root = nodeList.get(0);

		System.out.println("先序遍历：");
		preOrderTraverse(root);

		System.out.println();

		System.out.println("中序遍历：");
		inOrderTraverse(root);

		System.out.println();

		System.out.println("后序遍历：");
		postOrderTraverse(root);

		//权兴权意-2016.10.9
		System.out.println();
		System.out.println("计算结果：" + compDiameter(root));
	}

}

标签：

相关文章