剑指OfferJZ62:二叉搜索树的第k小个结点-java版

阳光穿透心脏的1/2处 2023-01-21 13:25 15阅读 0赞

### 剑指OfferJZ62：二叉搜索树的第k小个结点-java版 ###

*   *   *  JZ62:给定一棵二叉搜索树，请找出其中的第k小的TreeNode结点

### JZ62:给定一棵二叉搜索树，请找出其中的第k小的TreeNode结点 ###

**中序遍历**二叉树的每个节点，最终得到的序列是单调递增序列，那么第k次遍历到的节点就是第k小节点  
中序遍历：对于每一个节点，**先遍历当前节点的左孩子，接着遍历当前节点，最后遍历当前节点的右孩子**  
二叉树的三种遍历方法：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70 1]

中序遍历为：1,2,3,4,5,6 那么第k小节点（第三次遍历到的数）为3

public class Solution { 
       private TreeNode ans;//返回的最终的结果
        private int index;//标记中序遍历时当前节点是第几次遍历到的
    
        TreeNode KthNode(TreeNode pRoot, int k) { 
            //初始化变量
            index=1;
            ans=null;
            //中序遍历
            if(k!=0 && pRoot!=null) { 
                solve(pRoot, k);
            }
            return ans;
        }
    
        private void solve(TreeNode node,int k){ 
            if(ans==null) { 
                //先遍历当前节点的左孩子
                if (node.left != null) { 
                    solve(node.left, k);
                }
                if (index == k) { 
                    ans = node;
                }
                index++;
                //再遍历当前节点的右孩子
                if (node.right != null) { 
                    solve(node.right, k);
                }
            }
        }
    }

拓展：求二叉搜索树的第k大节点  
方法类似于上面  
这里是**先遍历当前节点的右孩子，接着遍历当前节点的，最后遍历当前节点的左孩子**（非二叉树遍历方法）

class Solution { 
        
         private TreeNode ans;//返回的最终的结果
        private int index;//标记中序遍历时当前节点是第几次遍历到的
    
        public int KthNode(TreeNode root, int k) { 
            //初始化变量
            index=1;
            ans=null;
            //中序遍历
            if(k!=0 && root!=null) { 
                solve(root, k);
            }
            return ans.val;
        }
    
        private void solve(TreeNode node,int k){ 
            if(ans==null) { 
                //先遍历当前节点的右孩子
                if (node.right != null) { 
                    solve(node.right, k);
                }
                //这里相当于遍历了当前节点
                if (index == k) { 
                    ans = node;
                }
                index++;
                //再遍历当前节点的左孩子
                if (node.left != null) { 
                    solve(node.left, k);
                }
            }
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][20210526112652679.gif_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70]: /images/20221020/61b12a09e6bd4d579ea0c1e756b96711.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70 1]: /images/20221020/4b87ea2aa40345678847cefac0aabe68.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTk5MjAyMQ_size_16_color_FFFFFF_t_70 2]: /images/20221020/fb64b881192a4d469a515e15b0a65b7b.png
[20210526112652679.gif_pic_center]: /images/20221020/5caa1f3810e045c9a28e128da2c55edb.png