/*求二叉樹中距離最遠的兩個點* 基本思路：* 遞歸計算兩棵樹的最大高度，設置一個全局變量，距離最遠的兩個節點element* 其中：在計算左子支，直接刷新上述全局變量，在計算右邊子支時，設置兩個臨時Node變量，變量里的element用于* 保存右邊子支的兩個最遠距離。根據比較兩個距離的大小、其父節點所在的樹三個的大小，來重新刷新全局變量。* 一個Trick~：在計算子支的最遠距離的時候，因為要和其父節點所在的樹比較大小，保存子支的最大距離的點數。 */public class MaxLenTree {public Node root;public int len = 0;public class Node {char element;int hight;Node left;Node right;public Node(char element, int hight, Node left, Node right) {this.element = element;this.hight = hight;this.left = left;this.right = right;}Node() {}}MaxLenTree() {/* Node e = new Node('e', 0, null, null);Node d = new Node('d', 0, e, null);Node f = new Node('f', 0, null, null);Node c = new Node('c', 0, d, f);Node b = new Node('b', 0, c, null);Node a = new Node('A', 0, b, null);*/Node m = new Node('m', 0, null, null);Node n = new Node('n', 0, null, null);Node k = new Node('k', 0, m, n);Node l = new Node('l', 0, null, null);Node i = new Node('i', 0, null, null);Node j = new Node('j', 0, k, l);Node q = new Node('q', 0, null, null);Node p = new Node('P', 0, q, null);Node h = new Node('h', 0, p, null);Node d = new Node('d', 0, h, null);Node e = new Node('e', 0, i, j);Node b = new Node('B', 0, d, e);Node f = new Node('f', 0, null, null);Node g = new Node('g', 0, null, null);Node c = new Node('c', 0, f, g);Node a = new Node('A', 0, b, c);root = a;}public static void main(String[] args) {MaxLenTree mTree = new MaxLenTree();mTree.calculateHight();mTree.run();}public void run() {Node node = new Node();System.out.println(findMaxLen(this.root, node));System.out.println("maxNode left.element---" + maxNodeleft.element);System.out.println("maxNoderight.element---" + maxNoderight.element);}public Node maxNodeleft = new Node();public Node maxNoderight = new Node();public int findMaxLen(Node root, Node LongestChild) {System.out.println(LongestChild.element);if (root.left == null && root.right == null) {LongestChild.element = root.element;maxNodeleft.element = root.element;maxNoderight.element = root.element;return 0;}Node leftLongestChild = new Node();Node rightLogestChild = new Node();if (root.left == null || root.right == null) {if (root.right == null) {int a = findMaxLen(root.left, leftLongestChild);System.out.println(leftLongestChild.element);if (hight(root) > a) {LongestChild.element = leftLongestChild.element;this.maxNodeleft.element = leftLongestChild.element;this.maxNoderight.element = root.element;return hight(root);} else {LongestChild.element = leftLongestChild.element;return a;}} else {int a = findMaxLen(root.right, rightLogestChild);if (hight(root) > a) {LongestChild.element = rightLogestChild.element;this.maxNodeleft.element = root.element;this.maxNoderight.element = rightLogestChild.element;return hight(root);} else {LongestChild.element = rightLogestChild.element;return a;}}}int a = findMaxLen(root.left, leftLongestChild);Node rightNodetempLeft = new Node();rightNodetempLeft.element = maxNodeleft.element;Node rightNodetempRight = new Node();rightNodetempRight.element = maxNoderight.element;int b = findMaxLen(root.right, rightLogestChild);int c = Math.max(a, b);if (a > b) {maxNodeleft.element = rightNodetempLeft.element;maxNoderight.element = rightNodetempRight.element;}if (c == b) {LongestChild.element = rightLogestChild.element;} else {LongestChild.element = leftLongestChild.element;}int d = hight(root.left) + hight(root.right) + 2;if (c < d) {maxNodeleft.element = leftLongestChild.element;maxNoderight.element = rightLogestChild.element;}System.out.println(LongestChild.element);return Math.max(c, d);}public int hight(Node root) {if (root == null) {return -1;}return root.hight;}public void showTree(Node root) {if (root == null) {return;}System.out.println(root.element + "<----->" + root.hight);showTree(root.left);showTree(root.right);}public void calculateHight() {calculateHight(this.root);}public int calculateHight(Node root) {if (root == null) {return -1;}if (root.right == null && root.left == null) {root.hight = 0;return 0;}int temp = Math.max(calculateHight(root.left),calculateHight(root.right)) + 1;root.hight = temp;return temp;}}

?

轉載于:https://www.cnblogs.com/lisongfeng9213/p/3806484.html

總結

以上是生活随笔為你收集整理的求一个二叉树中距离最远的两个节点的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。