leetcode 230.Kth Smallest Element in a BST-再帰|非再帰

原題リンク:230.Kth Smallest Element in a BST
【考え方-Java、Python】——再帰的実現
二分ルックアップ数(BST)の性質を知っています.いずれのノードの値も左サブツリーの任意のノード値より大きく、右サブツリーの任意のノード値より小さいです.これにより、最小値のノードがツリーの左端にあり、最大値のノードがツリーの右端にあることがわかります.木は小さい頃から大きい順に木の中序遍歴を満たす.したがって、従来の処理を中序遍で処理することができます.
kは基本タイプの数であるため、適用タイプとは異なり、今回の再帰的なk値の変化は次のラウンドの変化を引き起こさないことを知っています.では、私たちの処理方法はグローバル変数を増加したり、参照変数を増加したり、方法のパラメータを増加したりすることができます.このようなパラメータで現在遍歴しているのは数番目の数です.この問題では、ローカル変数を追加する方法を採用します.

public class Solution {
    private int count, res;
    public int kthSmallest(TreeNode root, int k) {
        if (root.left != null) kthSmallest(root.left, k);
        if (++count == k) res = root.val;     //①
        if (root.right != null) kthSmallest(root.right, k);
        return res;
    }
}

91/91
 test cases passed. Runtime: 1 ms  Your runtime beats 46.33% of javasubmissions.

class Solution(object):
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        global res, count
        res,count = 0,0
        def dfs(root, k) :
            if not root : return
            dfs(root.left, k)
            global count, res
            count += 1
            if count == k : res = root.val  //①
            dfs(root.right, k)
        dfs(root,k)
        return res

91/91
 test cases passed. Runtime: 100 ms  Your runtime beats 25.55% of pythonsubmissions.
【考え方-Java、Python】-非再帰的実現
非再帰的な実装にはスタックが必要です.非再帰的および再帰的な実装に慣れていない場合は、別のブログを参照してください. 
leetcode 94. Binary Tree Inorder Traversal 、leetcode 144. Binary Tree Preorder Traversal
詳細は次のとおりです.

public class Solution {
    public int kthSmallest(TreeNode root, int k) {
        int ret = 0;
        Stack stack = new Stack();
        while(true) {
            while(root != null) {
                stack.push(root);
                root = root.left;
            }
            if (stack.isEmpty()) break;
            root = stack.pop();
            if (--k == 0) return root.val;  //②
            root = root.right;
        }
        return 0;
    }

91/91
 test cases passed. Runtime: 2 ms  Your runtime beats 16.50% of javasubmissions.

class Solution(object):
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        stack = []
        res = 0
        while 1 :
            while root :
                stack.append(root)
                root = root.left
            if not stack : break
            root = stack.pop()
            k -= 1
            if k == 0 : return root.val  //②
            root = root.right
        return 0

91/91
 test cases passed. Runtime: 84 ms  Your runtime beats 72.03% of pythonsubmissions.
時間の複雑さについて言えば,時間の複雑さの対比は,本題の再帰と非再帰の対比によって,再帰と非再帰の違いを簡単に見ることができる.再帰では「再帰を終了」することはできず、returnを用いても再帰を終了することはできない.そのため、再帰を用いて各ノードを遍歴しなければならない.そのため、私たちは1で見つけたノードを記録し、時間の複雑さはO(n)である.再帰ではなく、k番目に大きいノードを見つけたら、私たちは直接2 returnで返しました.本題のように,再帰効率が非再帰よりも必ずしも低いとは限らないことが分かる.実際に空間複雑度,メソッドのスタックなどの動作を無視し,一時変数を直ちに解放できれば,再帰的な空間複雑度はさらに低い.
本題の基礎はやはりツリーの再帰と非再帰です.
leetcode 94. Binary Tree Inorder Traversal 、leetcode 144. Binary Tree Preorder Traversal