天天看點

【LeetCode】第501題——二叉搜尋樹中的衆數(難度:簡單)題目描述解題思路代碼詳解注意點

【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中序周遊。