golang 解法, 执行用时: 56 ms, 内存消耗: 9.4 MB, 提交时间: 2023-10-17 11:41:56

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func heightOfTree(root *TreeNode) int {
    ans := 0
    var dfs func(node *TreeNode, dpt int)
    dfs = func(node *TreeNode, dpt int) {
        if dpt > ans {
            ans = dpt
        }
        if node.Left != nil && node.Left.Right != node {
            dfs(node.Left, dpt+1)
        }
        if node.Right != nil && node.Right.Left != node {
            dfs(node.Right, dpt+1)
        }
    }
        
    dfs(root, 0)
    return ans
}

java 解法, 执行用时: 3 ms, 内存消耗: 42.7 MB, 提交时间: 2023-10-17 11:37:33

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int heightOfTree(TreeNode root) {
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        int level = 0;
        while (!queue.isEmpty()) {
            int m = queue.size();
            while (m-- > 0) {
                TreeNode node = queue.poll();
                if (node.left != null && node.left.right != node) queue.offer(node.left);
                if (node.right != null && node.right.left != node) queue.offer(node.right);
            }
            level++;
        }
        return level - 1;
    }
}

python3 解法, 执行用时: 228 ms, 内存消耗: 30.6 MB, 提交时间: 2023-10-17 11:36:57

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def heightOfTree(self, root: Optional[TreeNode]) -> int:
        # 每一个叶子节点还能有左右孩子
        # 如果他能被多次访问到就是叶子
        rec = set() # 记录是第几次被访问
        leaves = set() # 记录是否是叶子
        def dfs(node):
            if not node:
                return 
            if node.val in rec:
                leaves.add(node.val)
                return 
            rec.add(node.val)
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        
        ans = 0
        def getDepth(node, d):
            nonlocal ans 
            if not node:
                return
            if node.val in leaves: # 是叶子节点更新逻辑
                ans = max(ans, d)
                return 
            getDepth(node.left,d + 1)
            getDepth(node.right, d + 1)
        getDepth(root, 0)
            
        return ans

python3 解法, 执行用时: 200 ms, 内存消耗: 30.3 MB, 提交时间: 2023-10-17 11:36:16

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def heightOfTree(self, root: Optional[TreeNode]) -> int:
        ans = 0
        def dfs(node, dpt):
            nonlocal ans
            ans = max(ans, dpt)
            if node.left and node.left.right is not node:
                dfs(node.left, dpt+1)
            if node.right and node.right.left is not node:
                dfs(node.right, dpt+1)
        
        dfs(root, 0)
        return ans