二叉搜索树的第k个结点

梦里梦外; 2022-05-24 10:35 189阅读 0赞

![这里写图片描述][70]

import java.util.*;
     class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
    
        }
    
    }
    
    public class Solution {
         int count=0;
        //解法一:不要额外的空间
        TreeNode KthNode(TreeNode pRoot, int k)
        {
             if(pRoot==null||k<=0)
             {
                 return null;
             }
             if(pRoot!=null)
             {
                 TreeNode temp=KthNode(pRoot.left,k);
                 if(temp!=null)
                   return temp;
                 if(++count==k)
                   return pRoot;
                 temp=KthNode(pRoot.right,k);
                 if(temp!=null)
                   return temp;
             }
             return null;
        }
    
        //解法二：需要额外的空间
        TreeNode KthNode2(TreeNode pRoot, int k)
        {
            if(pRoot==null||k<=0)
               return null;
           ArrayList<Integer>arr=new ArrayList<>();
           inSearch(pRoot,arr);
           if(k>arr.size())
              return null;
           TreeNode  node=new TreeNode(arr.get(k-1));
           return node;
        }
    
        //二叉树的中序遍历
        public void inSearch(TreeNode root,ArrayList<Integer>arr)
        {
              if(root!=null)
              {
                 inSearch(root.left,arr);
                 //System.out.print(root.val);
                 arr.add(root.val);
                 inSearch(root.right,arr);
              }
    
        }
        public static void main(String[]args){
    
             //System.out.println("Hello");
               TreeNode root=new TreeNode(5);
               root.left=new TreeNode(3);
               root.right=new TreeNode(7);
               root.left.left=new TreeNode(2);
               root.left.right=new TreeNode(4);
               root.right.left=new TreeNode(6);
               root.right.right=new TreeNode(8);
               Solution s=new Solution();
               TreeNode node=s.KthNode(root,3);
               System.out.println(node.val);
    
        }
    
    
    }

![这里写图片描述][70 1]

[70]: /images/20220524/363d153ae8ea4b2da331532294f59c35.png
[70 1]: /images/20220524/344b733f1e4e4a01ab709723f6178e4a.png