Java中如何实现异构元组以避免二叉树最大深度迭代计算使用双栈

在求解LeetCode「二叉树的最大深度」题目的迭代版本时，Python可以直接在栈中存储(TreeNode, depth)结构的元组，仅用单个栈即可完成计算，但Java的常规实现会用两个栈分别存储节点和对应深度。Java本身没有内置元组类型，但我们可以通过以下两种方式实现类似的组合存储结构，避免使用双栈：

方案1：自定义静态辅助类（最推荐，类型安全无额外依赖） #

直接定义仅用来存储节点和对应深度的静态内部类，兼容性和可读性最高，实现代码如下：

class Solution {
    // 存储节点和对应深度的辅助类
    static class NodeDepth {
        TreeNode node;
        int depth;
        NodeDepth(TreeNode node, int depth) {
            this.node = node;
            this.depth = depth;
        }
    }

    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        Stack<NodeDepth> stack = new Stack<>();
        stack.push(new NodeDepth(root, 1));
        int maxDepth = 1;
        
        while (!stack.isEmpty()) {
            NodeDepth cur = stack.pop();
            if (cur.node.left != null) {
                stack.push(new NodeDepth(cur.node.left, cur.depth + 1));
            }
            if (cur.node.right != null) {
                stack.push(new NodeDepth(cur.node.right, cur.depth + 1));
            }
            maxDepth = Math.max(maxDepth, cur.depth);
        }
        return maxDepth;
    }
}

方案2：使用JDK自带AbstractMap.SimpleEntry（无需自定义类） #

如果不想单独编写辅助类，可以直接使用java.util.AbstractMap下的SimpleEntry存储键值对，JDK 1.6及以上版本都原生支持：

import java.util.AbstractMap;
import java.util.Stack;

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    Stack<AbstractMap.SimpleEntry<TreeNode, Integer>> stack = new Stack<>();
    stack.push(new AbstractMap.SimpleEntry<>(root, 1));
    int maxDepth = 1;
    
    while (!stack.isEmpty()) {
        AbstractMap.SimpleEntry<TreeNode, Integer> cur = stack.pop();
        TreeNode node = cur.getKey();
        int depth = cur.getValue();
        
        if (node.left != null) {
            stack.push(new AbstractMap.SimpleEntry<>(node.left, depth + 1));
        }
        if (node.right != null) {
            stack.push(new AbstractMap.SimpleEntry<>(node.right, depth + 1));
        }
        maxDepth = Math.max(maxDepth, depth);
    }
    return maxDepth;
}

两种方案的逻辑和Python版本完全对齐，运行效率和双栈实现没有明显差异，你可以根据自己的使用场景选择。

内容的提问来源于stack exchange，提问作者mol