76°

二叉搜索树的第 K 个节点

利用二叉查找树中序遍历有序的特点。

private TreeNode ret;
private int cnt = 0;

public TreeNode KthNode(TreeNode pRoot, int k) { inOrder(pRoot, k); return ret; }

private void inOrder(TreeNode root, int k) { if (root == null || cnt >= k) return; inOrder(root.left, k); cnt++; if (cnt == k) ret = root; inOrder(root.right, k); }

public class Solution {
   int index = 0; //计数器
    TreeNode KthNode(TreeNode root, int k)
    {
        if(root != null){ //中序遍历寻找第k个
            TreeNode node = KthNode(root.left,k);
            if(node != null)
                return node;
            index ++;
            if(index == k)
                return root;
            node = KthNode(root.right,k);
            if(node != null)
                return node;
        }
        return null;
    }
}

 

本文由【G】发布于开源中国,原文链接:https://my.oschina.net/u/3973793/blog/3130222

全部评论: 0

    我有话说: