Python怎么找到二叉搜索树中的所有mode

本篇内容介绍了“Python怎么找到二叉搜索树中的所有mode”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！

题目：找到二叉搜索树中的所有mode(出现最频繁的元素)。

思路：这里定义的二叉搜索树的一个结点的左子树中所有结点的值都小于或等于该结点的值，右子树则相反，大于或等于。于此同时，follow up说让我们不用除了递归中的隐含栈之外的额外空间，因此不能使用哈希表。由于是二叉搜索树，那么我们中序遍历出来的结果就是有序的，我们只需要比较前后两个元素是否相等，就能统计某个元素出现的次数，因为相同的元素可定是都在一起的。我们需要一个结点变量pre来记录上一个遍历到的结点，然后mx记录最大的次数，cnt计数当前元素出现的次数。中序遍历的时候，如果pre不为空，说明当前不是第一个结点，我们和之前一个结点比较，如果相等，则cnt自增1，如果不等，cnt重置1。如果此时cnt大于mx，那么我们清空结果res，并把当前结点值放入结果res，如果cnt等于mx，那么我们直接将当前结点值加入结果res，然后mx赋值为cnt。最后我们把pre更新为当前结点。如果pre为空，说明当前结点是根结点。那么我们新建一个结点并赋上当前结点值。

Language : cpp

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */class Solution {public:vector<int> findMode(TreeNode* root) {if (!root) return {};vector<int> res;
        TreeNode *now = root, *pre = NULL;stack<TreeNode*> s;int mx = 0, cnt = 1;while (!s.empty() || now) {while (now) {             //中序遍历，左中右。将每个结点的左子树入栈s.push(now);
                now = now->left;
            }
            now = s.top(); s.pop(); //取栈顶元素if (pre) {              //判断当前元素和上一个元素值是否一样，一样cnt计数加一cnt = (now->val == pre->val) ? cnt + 1 : 1;
            }                       //如果cnt大于等于mx，说明当前元素重复次数大于之前最大的重复元素的次数，需要将新结果入结果栈。if (cnt >= mx) {if (cnt > mx) res.clear();
                res.push_back(now->val);
                mx = cnt;
            }if (!pre) pre = new TreeNode(now->val);
            pre->val = now->val;
            now = now->right;
        }return res;
    }
};

Language : python

# Definition for a binary tree node.# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution(object):def findMode(self, root):"""
        :type root: TreeNode
        :rtype: List[int]
        """res = []
        s = []
        now = root
        pre = Nonemx, cnt = 0, 1while s or now:while now:
                s.append(now)
                now = now.left
            now = s.pop(len(s) - 1)if pre:if now.val == pre.val:
                    cnt = cnt + 1else:
                    cnt = 1if cnt >= mx:if cnt > mx:del res[:]
                res.append(now.val)
                mx = cntif not pre:
                pre = TreeNode(now.val)
            pre.val = now.val
            now = now.rightreturn res

“Python怎么找到二叉搜索树中的所有mode”的内容就介绍到这里了，感谢大家的阅读。如果想了解更多行业相关的知识可以关注亿速云网站，小编将为大家输出更多高质量的实用文章！