【LeetCode】第501題——二叉搜尋樹中的衆數（難度：簡單）

• 題目描述
• 解題思路
• 代碼詳解
• • 思路一：中序周遊+HashMap
  • 思路二：中序周遊(但不用記錄所有val的出現次數)
  • 思路三：Morris中序周遊+思路二
• 注意點

題目描述

給定一個有相同值的二叉搜尋樹（BST），找出 BST 中的所有衆數（出現頻率最高的元素）。

假定 BST 有如下定義：

結點左子樹中所含結點的值小于等于目前結點的值

結點右子樹中所含結點的值大于等于目前結點的值

左子樹和右子樹都是二叉搜尋樹

1. 示例：

   輸入： BST [1,null,2,2],

   1
    \
     2
    /
   2
              

   輸出：[2].

提示：如果衆數超過1個，不需考慮輸出順序

進階：你可以不使用額外的空間嗎？（假設由遞歸産生的隐式調用棧的開銷不被計算在内）

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/find-mode-in-binary-search-tree

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

解題思路

周遊方式都是基于中序周遊。

思路一：普通中序周遊，利用HashMap存儲出現過的val值和其出現次數。在HashMap中找出衆數。

思路二：普通中序周遊，利用BST的特性，中序周遊到的數字是按順序遞增的。也就是說如果目前數字等于上一個數字，則 ++count，若目前數字不等于上一數字，則count=1。然後比較count和max（max是最大出現次數）

思路三：Morris中序周遊，在加上思路二的存儲最大值思路。

這裡簡單說一下Morris中序周遊的步驟，因為樹的周遊結合動圖會更容易了解，但本人技術有限，是以具體理論不再此闡述。

• 如果cur無左子樹，cur向右移動(cur=cur.right)
• 如果cur有左子樹，找到cur左子樹上最右的節點，記為rightend
  • 如果rightend的right指針指向空，讓其(rightend的right指針)指向cur，cur向左移動(cur=cur.left)
  • 如果rightend的right指針指向cur，讓其(rightend的right指針)指向空，cur向右移動(cur=cur.right)

代碼詳解

思路一：中序周遊+HashMap

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    HashMap<Integer, Integer> hm;
    int max = 1;	// 0也可

    public int[] findMode(TreeNode root) {
        hm = new HashMap<>();
        Stack<Integer> stack = new Stack<>();	// 利用棧來存儲複數個衆數
        func(root);	// 中序周遊的遞歸寫法
        // 遞歸完後max也會得到，周遊HashMap的key，找到value==max的key，壓入stack中
        for(int i : hm.keySet()) {
            if(hm.get(i) == max) {
                stack.push(i);
            }
        }
        // stack的作用其實就是得到ints數組的長度
        int[] ints = new int[stack.size()];
        for(int i = 0; i < ints.length; ++i) {
            ints[i] = stack.pop();
        }
        return ints;
    }
	// 這個func的作用是中序周遊+更新HashMap+更新max
    public void func(TreeNode node) {
        if(node != null) {
        	// 更新HashMap
            if(hm.containsKey(node.val)) {
                hm.replace(node.val, hm.get(node.val)+1);
            } else {
                hm.put(node.val, 1);
            }
            // 更新max
            if(hm.get(node.val) > max) {
                max = hm.get(node.val);
            }
            // 中序周遊
            func(node.left);
            func(node.right);
        }
    }
}
           

思路二：中序周遊(但不用記錄所有val的出現次數)

class Solution {

    Stack<Integer> stack;
    int max = 0;	// 同一val出現的最大次數
    int base = 1;	// 上一個數，判斷目前數與上一個數是否相等，初值無所謂是多少
    int count = 0;	// 記錄目前數的出現次數，換了個base就得重置一遍count=1

    public int[] findMode(TreeNode root) {
        stack = new Stack<>();
        func(root);	// 中序周遊
        // stack已經在func中确定了，依次指派給ints即可
        int[] ints = new int[stack.size()];
        for(int i = 0; i < ints.length; ++i) {
            ints[i] = stack.pop();
        }
        return ints;
    }
	// 這個func的作用是中序周遊+更新count+更新base+更新max+更新stack
    public void func(TreeNode node) {
        if(node != null) {
        	// 中序周遊先是左
            func(node.left);
            // 中序周遊再是根
            if(node.val == base) {	// 目前數字和上一數字相同，則++count
                ++count;
            } else {	// 若不同則重置count=1并更改base
                count = 1;
                base = node.val;
            }
            // 若max變了，stack就得清除一遍，再壓入目前周遊的數字
            if(count > max) {
                max = count;
                stack.clear();
                stack.push(node.val);
            } else if(count == max) {	// 别忘了出現次數等于max的數字也需要入棧
                stack.push(node.val);
            }
            // 中序周遊最後是右
            func(node.right);
        }
    }
}
           

思路三：Morris中序周遊+思路二

class Solution {

	// 這裡與思路二一緻
    Stack<Integer> stack;
    int max = 0;
    int base = 1;
    int count = 0;

    public int[] findMode(TreeNode root) {
        stack = new Stack<>();
        // Morris中序周遊思路若有不懂則傳回上方解題思路章節
        TreeNode cur = root;		// 前驅節點cur
        TreeNode rightend = null;	// 左子樹最右的節點rightend

		// Morris中序周遊本體
		// 在新的周遊方法學會之後，還得知道什麼時候更新max、base、count、stack
		// 有一種情況比較好了解：周遊到最左的時候對cur進行更新，這點和普通中序周遊大體類似
		// 還有一種情況：rightend的right指針指向cur時，對cur進行更新，也就是傳回前驅節點時進行更新
        while(cur != null) {
        	// 如果cur無左子樹，cur向右移動(cur=cur.right)
            if(cur.left == null) {
                func(cur);
                cur = cur.right;
            // 如果cur有左子樹，找到cur左子樹上最右的節點，記為rightend
            } else {
                rightend = cur.left;
                while(rightend.right != null && rightend.right != cur) {
                    rightend = rightend.right;
                }
                // 如果rightend的right指針指向空，讓其指向cur，cur向左移動(cur=cur.left)
                if(rightend.right == null) {
                    rightend.right = cur;
                    cur = cur.left;
                // 如果rightend的right指針指向cur，讓其指向空，cur向右移動(cur=cur.right)
                } else if (rightend.right == cur) {
                    func(cur);
                    rightend.right = null;
                    cur = cur.right;
                }
            }
        }

		// stack裡存儲的都是衆數了
        int[] ints = new int[stack.size()];
        for(int i = 0; i < ints.length; ++i) {
            ints[i] = stack.pop();
        }
        return ints;
    }
	// 這個func的作用是更新count+更新base+更新max+更新stack
	// 說白了就是把思路二的左右子樹的遞歸給删去了
	// 因為主程式的外循環是while(cur != null)，是以實參一定不是null，不用考慮null的情況了
    public void func(TreeNode node) {
        if(node.val == base) {
            ++count;
        } else {
            count = 1;
            base = node.val;
        }
        if(count > max) {
            max = count;
            stack.clear();
            stack.push(node.val);
        } else if(count == max) {
            stack.push(node.val);
        }
    }
}
           

注意點

• 個人認為思路二就很可以了，再進階一點可以再額外掌握Morris中序周遊。