剑指offer_二叉搜索树的第k个节点

谁借莪１个温暖的怀抱￠ 2022-06-09 06:56 132阅读 0赞

/*
    题目描述
    给定一颗二叉搜索树，请找出其中的第k大的结点。
    例如， 5 / \ 3 7 /\ /\ 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。
    
    思路：
    二叉搜索树按照左根右遍历是由小到大
    按照左根右遍历每一个结点直到第k个
    
    要考虑k大于结点总数吗？此时会返回空
    
    k不使用静态就会出错，什么时候使用静态变量，什么时候使用参数传递？
    此处使用参数传递的话，k是按值传递，每次递归结束后并不会改变k的值
    */
    
    public  class KthNode {
    	static int kk;
    	static TreeNode pNode;
        static TreeNode kthNode(TreeNode pRoot, int k)
        {
            if (pRoot==null||k<=0)
            {
    			return null;
            }
            
            kk=k;
            kthNodeCore(pRoot);
            return pNode;
        }
       
    	private static void kthNodeCore(TreeNode pRoot) {
    	    if (pRoot==null)
            {
    			return;
            }
    	    
    	    if (pRoot.left!=null)
    		{
    	    	kthNodeCore(pRoot.left);
    		}
    	    
    	    kk--;
    	    if(kk==0)
    	    {
    	    	pNode=pRoot;
    	    	return;
    	    }
    	   
    		if (pRoot.right!=null)
    		{
    			kthNodeCore(pRoot.right);
    		}
    	}
    
    	public static void main(String[] args) 
    	{
    		TreeNode node5=new TreeNode(5);
    		TreeNode node3=new TreeNode(3);
    		TreeNode node7=new TreeNode(7);
    		TreeNode node2=new TreeNode(2);
    		TreeNode node4=new TreeNode(4);
    		TreeNode node6=new TreeNode(6);
    		TreeNode node8=new TreeNode(8);
    
    		node5.left=node3;
    		node5.right=node7;
    		node3.left=node2;
    		node3.right=node4;
    		node7.left=node6;
    		node7.right=node8;
    
    		System.out.println(kthNode(node5,3).val);
    	}
    }