Leetcode騰訊精選練習41 二叉搜尋樹中第K小的元素

原題：LeetCode230

點選跳轉

給定一個二叉搜尋樹，編寫一個函數 kthSmallest 來查找其中第 k 個最小的元素。

說明：

你可以假設 k 總是有效的，1 ≤ k ≤ 二叉搜尋樹元素個數。

示例1：

輸入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
輸出: 1
           

示例2：

輸入: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
輸出: 3

           

TreeNode定義

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

中序周遊

因為搜尋二叉樹有左節點值小于根節點小于右節點的性質，是以對線索二叉樹用中序周遊的話能得到整個二叉樹所有值的升序序列。利用這個性質來解答這道題，但是因為題目要求的是第K小元素，是以沒必要完全周遊整個二叉樹，可以用計數器Count來記錄周遊，當記錄到第K次時記錄答案即可

public class Solution {
             private  int res,count;

        public  int KthSmallest(TreeNode root, int k)
        {
            count = k;
            MidTraver(root);
            return res;
        }
        private  void MidTraver(TreeNode root)
        {
            if (root == null || count == 0)
                return;
            MidTraver(root.left);
            count--;
            if (count == 0)
                res = root.val;
            MidTraver(root.right);
        }   
    }