In this problem, you need to write an algorithm that stores values for each node of a binary tree and returns the height of the binary tree for a node with a specific value. The given binary tree is defined as follows:<\/p>\n
\n class TreeNode {\n int val;\n TreeNode left;\n TreeNode right;\n TreeNode(int x) { val = x; }\n }\n <\/pre>\nProblem: Calculate the height for a specific value in a binary tree<\/h3>\n
You are given the root node of a binary tree and a specific value target<\/code>. Return the height of the node with target<\/code> in the binary tree. The height of a node is defined as the length of the longest path from that node to a leaf node. If there is no node with the target value, return -1.<\/p>\nInput<\/h3>\n\nTreeNode root<\/code>: the root node of the binary tree<\/li>\nint target<\/code>: the value to search for<\/li>\n<\/ul>\nOutput<\/h3>\n\n- The height of the target, or -1 if the target cannot be found<\/li>\n<\/ul>\n<\/div>\n\n
Solution Method<\/h2>\n
To solve this problem, you first need to understand and implement an algorithm to calculate the height of a binary tree. You will design the algorithm to traverse the tree using depth-first search (DFS) and find the node that matches the target value, returning the height of that node.<\/p>\n
Step-by-Step Solution<\/h3>\n\n- \nUnderstand the structure of a binary tree:<\/strong> A binary tree is a tree structure where each node can have at most two child nodes. Each node stores data.\n <\/li>\n
- \nImplement depth-first search (DFS):<\/strong> Recursively traverse the data to find the target node.\n <\/li>\n
- \nCalculate the height:<\/strong> When the target node is found, calculate the maximum depth from that node to a leaf.\n <\/li>\n
- \nReturn the result:<\/strong> If the target node is found, return its height; if not, return -1.\n <\/li>\n<\/ol>\n
Java Code Implementation<\/h3>\n\n public class Solution {\n public int findHeight(TreeNode root, int target) {\n return findNodeHeight(root, target, 0);\n }\n\n private int findNodeHeight(TreeNode node, int target, int depth) {\n if (node == null) {\n return -1; \/\/ Return -1 if the node is null\n }\n \n \/\/ If the current node is the target node\n if (node.val == target) {\n return getHeight(node);\n }\n \n \/\/ If not a leaf node, search the child nodes\n int leftHeight = findNodeHeight(node.left, target, depth + 1);\n int rightHeight = findNodeHeight(node.right, target, depth + 1);\n\n \/\/ If the target node is found in the left node, return its height\n if (leftHeight != -1) {\n return leftHeight;\n }\n \/\/ If the target node is found in the right node, return its height\n return rightHeight;\n }\n\n private int getHeight(TreeNode node) {\n if (node == null) return -1; \/\/ For leaf nodes, depth is -1\n \n \/\/ Recursively calculate the depth of left and right subtrees\n int leftHeight = getHeight(node.left);\n int rightHeight = getHeight(node.right);\n \n \/\/ Return the maximum depth from the current node to a leaf\n return Math.max(leftHeight, rightHeight) + 1;\n }\n }\n <\/pre>\nCode Explanation<\/h3>\n
In the code above, the findHeight<\/code> method takes the root node and target value as arguments and searches for the node. findNodeHeight<\/code> recursively traverses each node to find the target value and calculate its height. The getHeight<\/code> method is called to calculate the depth of a specific node.<\/p>\nExample<\/h3>\n
Consider the following binary tree.<\/p>\n
\n 1\n \/ \\\n 2 3\n \/ \\\n 4 5\n <\/pre>\n