63 二叉搜索树中的第k个节点（中序遍历递归_有返回值-无返回值；Java对象作为参数）

103 阅读 0 评论 68 点赞

我是靠谱客的博主碧蓝薯片，最近开发中收集的这篇文章主要介绍63 二叉搜索树中的第k个节点（中序遍历递归_有返回值-无返回值；Java对象作为参数），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目描述

给定一颗二叉搜索树，请找出其中的第k大的结点。
例如， 5 
     / 
    3   7 
   /   /
  2  4 6  8
 中，按结点数值大小顺序第三个结点的值为4。

一开始，我打算使用count计数的方法，当count的数等于k的时候，就是要返回的结果。很容易就写出来了，但是总是报错（TreeNode res的形式）。怎么回事呢？？？尚不明白===》即递归遍历的时候什么时候返回值，什么时候不返回值？
发现改为数组就对了，前面两种有点懵。
（1）

import java.util.*;
public class Solution {
    int count = 0;
     void InOrder(TreeNode pRoot,int k, TreeNode[] res){
        if(pRoot != null){
            InOrder(pRoot.left,k,res);
            count++;
            if(count == k)
                res[0] = pRoot;
            InOrder(pRoot.right,k,res);
        }                 

    }
    TreeNode KthNode(TreeNode pRoot, int k)
    {
        TreeNode[] res = new TreeNode[1];
        InOrder(pRoot,k,res);
        return res[0];        
    }
}

从这组，我终于明白了java的参数传递，当传递基本参数类型时，是值传递，只把值复制一下，不会相互影响；但是当传递的是一个对象的时候，这时候传递的是地址（实参指向的地址），而不是引用。例子如下：

public class Test {
    public static void main(String[] args) {
        Node node = new Node(4);
        function(node);//实参node
        System.out.println(node.val);
    }
    public static void function(Node node){//形参node
        //Node node3 = new Node(7);//无影响
        //node = node3;
        node.val = 9;//有影响
    }
   static class Node{
        int val = 0;
        public Node(int val)
        {
            this.val = val;
        }
    }
}

实参node只是把node指向对象的地址传递给了形参，也就是说这时候，实参（栈地址a）和形参(栈地址b)都各自在栈中占用一块地址，然后同时指向同一个对象（堆地址c）。

此时，如果形参改变了对象本身的属性，当然这会影响实参的；但是，如果形参指向了新的对象node3，只是说明形参指向了新的对象（堆地址d），而实参仍然会指向以前的对象（堆地址a），不会发生任何影响！

所以，在第一种递归格式中，要使用一个TreeNode[] 数组来保存值，而不能使用TreeNode的引用，或者有返回值。

（2）有返回值的形式，这样就不用使用数组了。

import java.util.*;
public class Solution {
    int count = 0;
     TreeNode InOrder(TreeNode pRoot,int k){
        if(pRoot != null){
            TreeNode res = InOrder(pRoot.left,k );
            if(res != null)
                return res;
            count++;
            if(count == k)
                return pRoot;
            res = InOrder(pRoot.right,k );
            if(res != null)
                return res;
        }                 
       return null;
    }
    TreeNode KthNode(TreeNode pRoot, int k)
    {       
        return InOrder(pRoot,k);        
    }
}

if(res != null) return res;，这是因为递归中，一旦某个地方返回了值，后面就不能进行修改了，所以，只要不为null，就把下面递归得到的值直接返回。

（3）最下面这个简单，只是遍历一遍存到数组里面即可

import java.util.*;
public class Solution {
    int count = 0;
    ArrayList<TreeNode> list = new ArrayList();
    void InOrder(TreeNode pRoot){
        if(pRoot != null){
            InOrder(pRoot.left);
            list.add(pRoot);
            InOrder(pRoot.right);
        }                 

    }
    TreeNode KthNode(TreeNode pRoot, int k)
    {
        InOrder(pRoot );
        for(int i=0;i<list.size();i++){
            if(i == k-1)
                return list.get(i);
        }
        return null;
    }


}