# 二叉树求最短路径，高度，最大宽度

2018/11/10 15:49

package com.weshare.eel.task.utils;

import com.jayway.jsonpath.internal.function.numeric.Max;

import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;

public class FindShortestPath2 {

private static boolean isLeafFind = false;

private static String path1;

public static void main(String[] args) {

TreeNode node1 = new TreeNode(1);
TreeNode node2 = new TreeNode(2);
TreeNode node3 = new TreeNode(3);
TreeNode node4 = new TreeNode(4);
TreeNode node5 = new TreeNode(5);
TreeNode node6 = new TreeNode(6);
TreeNode node7 = new TreeNode(7);
TreeNode node8 = new TreeNode(8);

node5.setLeft(node2);
node5.setRight(node7);
node7.setLeft(node6);
node7.setRight(node8);
node2.setLeft(node1);
node2.setRight(node3);
node3.setRight(node4);

//findPathOfTwoNode(node5, node3, node6);
Stack<Integer> path = new Stack<Integer>();
findPath(node5, path);

System.out.println(path);
System.out.println(findHeight(node5));
System.out.println(findWidth(node5));
}

private static int findWidth(TreeNode root) {
if (root == null) {
return 0;
}

int maxWidth = 1;

Queue<TreeNode> path = new ArrayDeque<>();

while (true) {
int len = path.size();
if (len == 0) {
break;
}
while (len > 0) {
TreeNode node = path.poll();
len--;

if (node.getLeft() != null) {
}

if (node.getRight() != null) {
}
}

maxWidth = Math.max(maxWidth, path.size());
}

return maxWidth;
}

public static int findHeight(TreeNode root) {
if (root == null) {
return 0;
}

int left = findHeight(root.getLeft());
int right = findHeight(root.getRight());

return 1 + Math.max(left, right);
}

public static void findPath(TreeNode root, Stack<Integer> path) {
if (root == null) {
return;
}
path.push(root.getValue());

if (root.getLeft() != null) {
findPath(root.getLeft(), path);
}

//查询右子树
if (root.getRight() != null) {

findPath(root.getRight(), path);
}

}

public static String findPath(TreeNode root, Stack<Integer> path, TreeNode nodeToFind) {
if (root == null) {
return null;
}

path.push(root.getValue());
if (!isLeafFind && nodeToFind == root) {
isLeafFind = true;
path1 = printPath(path);
return path1;
}

if (!isLeafFind && root.getLeft() != null) {
findPath(root.getLeft(), path, nodeToFind);
}

//查询右子树
if (!isLeafFind && root.getRight() != null) {

findPath(root.getRight(), path, nodeToFind);
}

//如果没找到则弹栈
if (!isLeafFind) {
path.pop();
}

return path1 == null ? null : path1;

}

public static String printPath(Stack<Integer> path) {

int len = path.size();
String s = "" + path.pop();
for (int i = 1; i < len; i++) {

if (path.peek() != null) {

s += "->" + path.pop();

}
}
System.out.println(s);

return s;
}

public static TreeNode findCommonParent(TreeNode root, TreeNode p, TreeNode q) {
if (root == null || root == p || root == q) {
return root;
}

TreeNode left = findCommonParent(root.getLeft(), p, q);
TreeNode right = findCommonParent(root.getRight(), p, q);

if (left != null && right != null) {
return root;
}

return left == null ? right : left;
}

private static void findPathOfTwoNode(TreeNode root, TreeNode p, TreeNode q) {

Stack<Integer> path1 = new Stack<Integer>();
Stack<Integer> path2 = new Stack<Integer>();

//寻找两个路径的交点，即最小公共祖先
TreeNode lca = findCommonParent(root, p, q);
//得到p节点的路径
System.out.println("最小公共祖先节点" + lca.getValue() + "和节点" + p.getValue() + "之间的路径");
String s1 = findPath(lca, path1, p);
isLeafFind = false;//全局变量复位
//得到q节点的路径
System.out.println("最小公共祖先节点" + lca.getValue() + "和节点" + q.getValue() + "之间的路径");
String s2 = findPath(lca, path2, q);
isLeafFind = false;//全局变量复位

//合并两条路径去掉重复的最小公共祖先
String[] split = s2.split("->");
String s3 = s1 + "->" + split[0];

for (int i = 1; i < split.length; i++) {

if (Integer.parseInt(split[i]) != lca.getValue()) {

s3 += "->" + split[i];
}

}

System.out.println("归并后的路径为：" + s3);

}
}

package com.weshare.eel.task.utils;

public class TreeNode {
private int value;
private TreeNode left;
private TreeNode right;

public TreeNode(int value) {
this.value = value;
}

public int getValue() {
return value;
}

public void setValue(int value) {
this.value = value;
}

public TreeNode getLeft() {
return left;
}

public void setLeft(TreeNode left) {
this.left = left;
}

public TreeNode getRight() {
return right;
}

public void setRight(TreeNode right) {
this.right = right;
}

}

0
0 收藏

0 评论
0 收藏
0