华为OD机试 - 计算三叉搜索树的高度（Java & JS & Python & C & C++）

题目：计算三叉搜索树的高度。

解法：三叉搜索树的高度是其最长路径的长度。可以通过中序遍历来找到这个最长路径。

Java 代码示例：

class Solution {
    int maxHeight = 0;
 
    public int getHeight(TreeNode root) {
        helper(root);
        return maxHeight;
    }
 
    private void helper(TreeNode node) {
        if (node == null) {
            return;
        }
        helper(node.left);
        maxHeight = Math.max(maxHeight, getCurrentHeight(node));
        helper(node.right);
    }
 
    private int getCurrentHeight(TreeNode node) {
        int leftHeight = node.left == null ? 0 : node.left.height;
        int rightHeight = node.right == null ? 0 : node.right.height;
        return 1 + Math.max(leftHeight, rightHeight);
    }
}

JavaScript 代码示例：

/**
 * @param {TreeNode} root
 * @return {number}
 */
var getHeight = function(root) {
    let maxHeight = 0;
    dfs(root);
    return maxHeight;
 
    function dfs(node) {
        if (node === null) {
            return;
        }
        dfs(node.left);
        maxHeight = Math.max(maxHeight, getCurrentHeight(node));
        dfs(node.right);
    }
 
    function getCurrentHeight(node) {
        const leftHeight = node.left === null ? 0 : node.left.height;
        const rightHeight = node.right === null ? 0 : node.right.height;
        return 1 + Math.max(leftHeight, rightHeight);
    }
};

Python 代码示例：

class Solution:
    def getHeight(self, root: 'TreeNode') -> int:
        self.max_height = 0
        self.helper(root)
        return self.max_height
 
    def helper(self, node: 'TreeNode'):
        if not node:
            return
        self.helper(node.left)
        self.max_height = max(self.max_height, self.get_current_height(node))
        self.helper(node.right)
 
    def get_current_height(self, node: 'TreeNode'):
        left_height = 0 if node.left is None else node.left.height
        right_height = 0 if node.right is None else node.right.height
        return 1 + max(left_height, right_height)

C 代码示例：

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    // 假设每个节点都有一个额外的字段height表示其高度
};
 
int maxHeight = 0;
 
void helper(struct TreeNode* node) {
    if (node == NULL) {
        return;
    }
    helper(node->left);
    maxHeight = MAX(maxHeight, getCurrentHeight(node));
    helper(node->right);
}
 
int getCurrentHeight(str