During the interview, I encountered a question: How to find the furthest leaf node of a binary tree, and the distance from this leaf node to the root node?
The first reaction is definitely recursion
How can we find the farthest leaf node and also record the distance from this leaf node to the root node? Use a List to maintain the path from the root node to the leaf node. The length of this list is -1, which is the distance from the leaf node to the root node. The last node of the list is to the leaf node.
I don't need to design a binary tree. See another article for specific codes.
/** * Find the furthest leaf node*/ public void findFarestLeaf() { List<Node> path = new ArrayList<Node>(); List<Node> longestPath = findLongestPath(root, path); Node leaf = longestPath.get(longestPath.size() - 1); System.out.println("The furthest leaf node is <" + leaf.key + ", " + leaf.value + ">, and the distance to the root node is: "+(longestPath.size() - 1)); } public List<Node> findLongestPath(Node x, List<Node> path) { if (x == null) return path; // Every recursion must be created, otherwise the recursive branches will be done on the same list. In fact, all nodes are added to this list. List<Node> currPath = new ArrayList<Node>(); currPath.addAll(path); currPath.add(x); List<Node> leftPath = findLongestPath(x.left, currPath); List<Node> rightPath = findLongestPath(x.right, currPath); if (leftPath.size() > rightPath.size()) return leftPath; else return rightPath; }The above article searching for the furthest leaf node (example explanation) of the binary tree is all the content I share with you. I hope it can give you a reference and I hope you can support Wulin.com more.