介紹

中序遍歷：左子樹 -> 中 -> 右子樹

二叉搜索樹：中序遍歷可以得到有序的序列

遞歸法

1.使用函數循環遞歸處理

2.使用一個數組來保存 k, 保證在個個遞歸函數中都能看到 看的變化；每訪問一個節點，這個數減一，當數組中的數為1時，即訪問到了第k小的數

/*** Definition for a binary tree node.* public class TreeNode {*     public int val;*     public TreeNode left;*     public TreeNode right;*     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
public class Solution {public int KthSmallest(TreeNode root, int k) {// 輔助結構，當 k == 1 時 表示訪問到 第 k個最小的元素int[] aux = new int[] { k };return Traverse(root, aux);    }// 遞歸訪問public int Traverse(TreeNode node, int[] aux) {if(node == null){// 用 -1 表示訪問到終點return -1;}// 先訪問左子樹{var val = Traverse(node.left, aux);if(val != -1){return val;}}// 訪問該節點{if(aux[0] == 1){// 結果return node.val;}aux[0]--;}// 后訪問右子樹{var val = Traverse(node.right, aux);if(val != -1){return val;}}// 這里是不會走到的根據題意return -1;}
}

優化：

1.使用 引用傳遞 k, 確保遞歸函數都能看到k的變換

2.每次訪問右子樹時，不用判斷直接返回結果

/*** Definition for a binary tree node.* public class TreeNode {*     public int val;*     public TreeNode left;*     public TreeNode right;*     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
public class Solution {public int KthSmallest(TreeNode root, int k) {// 輔助結構，當 k == 1 時 表示訪問到 第 k個最小的元素int aux = k;return Traverse(root, ref aux);    }// 遞歸訪問public int Traverse(TreeNode node, ref int aux) {if(node == null){// 用 -1 表示訪問到終點return -1;}// 先訪問左子樹{var val = Traverse(node.left, ref aux);if(val != -1){return val;}}// 訪問該節點{if(aux == 1){// 結果return node.val;}aux--;}// 后訪問右子樹// {//     var val = Traverse(node.right, ref aux);//     if(val != -1)//     {//         return val;//     }// }// // 這里是不會走到的根據題意// return -1;// 一個優化，這里直接返回，如果沒找到這里就返回-1return Traverse(node.right, ref aux);}
}

迭代法

1.使用數據結構Stack，模擬真實的棧處理流程

/*** Definition for a binary tree node.* public class TreeNode {*     public int val;*     public TreeNode left;*     public TreeNode right;*     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
public class Solution {public int KthSmallest(TreeNode root, int k) {// 借助 Stack 模擬棧Stack<TreeNode> s = new Stack<TreeNode>();// 先讓第一個節點進棧，后面流程就處理一致了s.Push(root);// 根據題意一定存在結果// while(s.Count > 0)while(true){// 訪問左子樹var top = s.Peek();if(top != null){s.Push(top.left);continue;}// 將null節點彈出棧s.Pop();// 訪問當前節點，這里不用判斷 s的數量，根據代碼可知，這里至少存在一個節點var visit = s.Pop();if(k == 1){// 第k最小元素return visit.val;}k--;// 訪問右子樹s.Push(visit.right);}return -1;}
}