《程序員代碼面試指南》第三章 二叉樹問題 二叉樹節點間的最大距離問題

題目

二叉樹節點間的最大距離問題

java代碼

package com.lizhouwei.chapter3;/*** @Description:二叉樹節點間的最大距離問題* @Author: lizhouwei* @CreateDate: 2018/4/16 19:33* @Modify by:* @ModifyDate:*/
public class Chapter3_20 {public int maxDistance(Node head) {int[] record = new int[1];return postOrder(head, record);}public int postOrder(Node head, int[] record) {if (head == null) {record[0] = 0;return 0;}int lM = postOrder(head.left, record);//head的左子樹中最遠的距離int leftMax = record[0];//head的左子樹離葉子節點最遠的距離int rM = postOrder(head.right, record);//head的右子樹中最遠的距離int righMax = record[0];//head的右子樹離葉子節點最遠的距離//head左右子樹離葉子節點最遠的距離最大的一個，再加上1 就是此節點中里葉子節點最大的距離record[0] = Math.max(leftMax, righMax) + 1;int curMax = leftMax + righMax + 1;//通過head節點的距離return Math.max(Math.max(lM, rM), curMax);}//測試public static void main(String[] args) {Chapter3_20 chapter = new Chapter3_20();int[] arr = {4, 2, 5, 1, 3, 6, 7};Node head = NodeUtil.generTree(arr, 0, arr.length - 1);System.out.print("head二叉樹節點間最大距離為：" + chapter.maxDistance(head));}
}