InfoTree二叉树转无重复字符栈及匹配最大数值对应字符问题

嘿，我来帮你捋捋这个问题～你已经实现了递归查找最大number的函数，现在要匹配对应的character，还考虑转成无重复character的栈来解决，这个思路可行，但其实还有更高效直接的方案，我给你两种思路参考：

思路一：递归过程中直接追踪最大number和对应character #

既然你已经在递归遍历树找最大number，那完全可以在这个过程中同时记录当前最大number对应的character，不用额外做一次遍历或者转栈。这样时间和空间效率都更高。

假设你的InfoTree节点结构是这样的（以Java为例，其他语言逻辑类似）：

class InfoTree {
    int number;
    char character;
    InfoTree left;
    InfoTree right;

    // 构造函数、getter/setter等
}

你可以用一个引用类型（比如数组、自定义对象）来在递归中传递当前的最大状态，比如：

// 递归函数：遍历树，更新最大number和对应的character
public void trackMaxWithChar(InfoTree root, int[] maxRecord) {
    if (root == null) return;

    // 如果当前节点的number比记录的最大值大，更新最大值和对应character
    if (root.number > maxRecord[0]) {
        maxRecord[0] = root.number;
        maxRecord[1] = root.character;
    }

    // 递归遍历左右子树
    trackMaxWithChar(root.left, maxRecord);
    trackMaxWithChar(root.right, maxRecord);
}

// 调用方式
public char getMaxNumberChar(InfoTree root) {
    // maxRecord[0]存最大number，初始为最小整数；maxRecord[1]存对应character
    int[] maxRecord = new int[]{Integer.MIN_VALUE, '\0'};
    trackMaxWithChar(root, maxRecord);
    return (char) maxRecord[1];
}

这个方案的时间复杂度是O(n)（每个节点遍历一次），空间复杂度是O(h)（h是树的高度，递归栈的深度），非常高效。

思路二：用栈遍历树+去重映射实现你的想法 #

如果你坚持想用栈的方式来处理，那可以先通过栈遍历整个二叉树，同时构建一个character到对应最大number的映射（自动处理character重复的情况，只保留每个character的最大number），最后再从映射里找出最大number对应的character。

代码示例：

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public char getMaxNumberCharWithStack(InfoTree root) {
    if (root == null) throw new IllegalArgumentException("树不能为空");

    Map<Character, Integer> charMaxMap = new HashMap<>();
    Stack<InfoTree> stack = new Stack<>();
    stack.push(root);

    // 栈遍历二叉树（这里用前序遍历，其他遍历方式也可以）
    while (!stack.isEmpty()) {
        InfoTree node = stack.pop();
        char currentChar = node.character;
        int currentNum = node.number;

        // 更新当前character的最大number：如果不存在或者当前number更大，就替换
        if (!charMaxMap.containsKey(currentChar) || currentNum > charMaxMap.get(currentChar)) {
            charMaxMap.put(currentChar, currentNum);
        }

        // 先压右子树，再压左子树，保证左子树先被处理（前序遍历顺序）
        if (node.right != null) stack.push(node.right);
        if (node.left != null) stack.push(node.left);
    }

    // 从映射中找出最大number对应的character
    int maxNum = Integer.MIN_VALUE;
    char targetChar = '\0';
    for (Map.Entry<Character, Integer> entry : charMaxMap.entrySet()) {
        if (entry.getValue() > maxNum) {
            maxNum = entry.getValue();
            targetChar = entry.getKey();
        }
    }

    return targetChar;
}

这个方案的时间复杂度也是O(n)，但空间复杂度是O(n)（栈和映射的存储空间），好处是可以额外得到每个character对应的最大number，适合后续有其他需求的场景。

不管选哪种方案，都能解决你的问题～如果你的树是其他语言实现的（比如Python、C++），只需要把语法调整一下，核心逻辑是一样的。

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