38. 树

您所在的位置：网站首页 › 统计出出现次数最多的值 › 38. 树

38. 树

2024-07-13 01:12| 来源: 网络整理| 查看: 265

1.题目

LeetCode: 501. 二叉搜索树中的众数

【easy】

给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。

假定 BST 有如下定义：

结点左子树中所含结点的值小于等于当前结点的值

结点右子树中所含结点的值大于等于当前结点的值

左子树和右子树都是二叉搜索树

例如：

给定 BST [1,null,2,2],

1 2 / 2 返回[2].

提示：如果众数超过1个，不需考虑输出顺序

进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

2.解题方法一：中序遍历

根据二叉搜索树的性质，其中序遍历的结果即是元素节点按大小顺序排列的结果，所以在所有相同的节点必定相邻，故在中序遍历的基础上对相同节点进行计数，将所有众数的节点放入list中，然后将其放入数组进行返回即可。

java：

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int[] findMode(TreeNode root) { int cur_count = 1; int max_count = 1; TreeNode pre_node = null; List list = new ArrayList(); Stack stack = new Stack(); TreeNode cur = root; while (cur != null || !stack.isEmpty()) { while (cur != null) { stack.push(cur); cur = cur.left; } TreeNode node = stack.pop(); if (pre_node != null) { if (pre_node.val == node.val) cur_count++; else cur_count = 1; } if (cur_count > max_count) { max_count = cur_count; list.clear(); list.add(node.val); } else if (cur_count == max_count) { list.add(node.val); } pre_node = node; cur = node.right; } int[] res = new int[list.size()]; int i = 0; for (int num : list) { res[i++] = num; } return res; } }

时间复杂度：O(n)

空间复杂度：O(n)

*方法二：Morris 中序遍历

java：

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { int base, count, max_count; List list = new ArrayList(); public int[] findMode(TreeNode root) { TreeNode cur = root, pre = null; while (cur != null) { if (cur.left == null) { update(cur.val); cur = cur.right; continue; } pre = cur.left; while (pre.right != null && pre.right != cur) { pre = pre.right; } if (pre.right == null) { pre.right = cur; cur = cur.left; } else { pre.right = null; update(cur.val); cur = cur.right; } } int[] res = new int[list.size()]; int i = 0; for (int num : list) { res[i++] = num; } return res; } public void update(int x) { if (x == base) { ++count; } else { count = 1; base = x; } if (count == max_count) { list.add(base); } if (count > max_count) { max_count = count; list.clear(); list.add(base); } } }

时间复杂度：O(n)

空间复杂度：O(1)

3.相关知识 1.Morris Traversal方法遍历二叉树（非递归，不用栈，O(1)空间）

https://www.cnblogs.com/AnnieKim/archive/2013/06/15/MorrisTraversal.html

【本文地址】

38. 树

38. 树

今日新闻

推荐新闻