【二叉树专题】剑指 Offer 54. 二叉搜索树的第k大节点-跟着帅地玩副业，开拓第二曲线PlayOffer

岱永久会员 2025年1月8日下午3:30

LCR 174. 寻找二叉搜索树中的目标节点

class Solution {
    int cnt,res;
    public int findTargetNode(TreeNode root, int cnt) {
        this.cnt = cnt;
        dfs(root);
        return res;
    }
    void dfs(TreeNode root){
        if(root==null)return;
        dfs(root.right);
        if(cnt==0)return;
        cnt--;
        if(cnt == 0)res = root.val;
        dfs(root.left);
    }
}

0 赞同 0 条回复

mpweixin用户普通 2024年12月23日下午6:15

class Solution {
public:
    int findTargetNode(TreeNode* root, int cnt) {
        vector<int> iorder = inorder(root);
        if(iorder.size() < cnt) return -1;
        return iorder[iorder.size() - cnt];
    }
    vector<int> inorder(TreeNode* root){ //中
        stack<TreeNode*> st;
        vector<int> result;
        TreeNode* cur = root;
        while(cur || !st.empty()){
            if(cur){
                st.push(cur);
                cur = cur->left;
            }
            else{
                cur = st.top();
                st.pop();
                result.push_back(cur->val);
                cur = cur->right;
            }
        }
        return result;
    }
};

依据中序结果即可求得二叉搜索树的第n大结果

0 赞同 0 条回复

Pendulumpal 普通 2024年12月17日下午9:33

中序遍历

class Solution {
    LinkedList<Integer>arr=new LinkedList<Integer>();
    private void dfs(TreeNode root){
        if(root==null)return;
        dfs(root.left);
        arr.add(root.val);
        dfs(root.right);
    }
    public int findTargetNode(TreeNode root, int cnt) {
        dfs(root);
        return arr.get(arr.size()-cnt);
    }
}

0 赞同 0 条回复

youngsir 普通 2024年12月11日上午9:48

二叉搜索树中序遍历是递增的，先中序遍历再根据K找

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
    vector<int> num;
public:
    int findTargetNode(TreeNode* root, int cnt) {

        getdata(root);
        return num[num.size()-cnt];

    }
    void getdata(TreeNode* root){
        if(!root) return;
        getdata(root->left);
        num.push_back(root->val);
        getdata(root->right);
    }
};

0 赞同 0 条回复

陆狗陆狗普通 2024年12月7日下午2:07

解题思路
– 搜索二叉树，左->中->右，升序排列；右->中->左，降序排列；
– 使用递归进行遍历
– 通过全局变量，可以去记录当前已经遍历到的节点个数，一旦达到目标前n大的时候，程序结束
【题解1】

class Solution {
    // 定义全局变量，这样递归可以使用公共的变量判断
    int cnt = 0;
    int target = 0;

    public int findTargetNode(TreeNode root, int cnt) {
        if (cnt <= 0) {
            return target;
        }
        this.cnt = cnt;
        // 遍历到最右侧，然后按照右-》中-》左，遍历到第几个就是第几大
        search(root);
        return target;

    }

    public void search(TreeNode root) {
        // 这里cnt为什么要<0,因为递归回到外层时，cnt--,回导致cnt<0。
        if (root == null || cnt <= 0) {
            return;
        }
        // 右下角
        search(root.right);
        // 右下角第一个元素（能执行cnt--操作，一定是不为null的元素）
        cnt--;
        if(cnt==0){
            // 这里如果不Return，会导致递归回到外层时，cnt--，cunt=-1时，target的值变化
            target = root.val;
            return;
        }
        // 第一个元素的左子树
        search(root.left);
    }

}

0 赞同 0 条回复

晓宇普通 2024年12月3日下午8:18

class Solution {
public:
    int k;
    int ans;
    int findTargetNode(TreeNode* root, int cnt) {
        this->k = cnt;
        rit_root_lef(root);
        return ans;
    }

    void rit_root_lef(TreeNode* root){
        if(root == nullptr || k <= 0) return ;
        rit_root_lef(root->right);
        this->k --;
        if(k == 0) ans = root->val;
        rit_root_lef(root->left);
    }
    // 思路：利用中序遍历（左 根 右），因为二叉搜索树是有序序列，且左根右对应节点的值具有从小到大的关系。要寻找第cnt大的节点，先遍历右节点即可。
    // 时间复杂度：o(n)；空间复杂度:o(log n)
};

0 赞同 0 条回复

Aatorx 永久会员 2024年12月3日下午3:09

class Solution {
public:
    int findTargetNode(TreeNode* root, int cnt) {
        int res = 0;
        dfs(root, cnt, res);
        return res;
    }
    void dfs(TreeNode* root, int& cnt, int& res){
        if (root == nullptr || cnt <= 0){
            return;
        }
        dfs(root->right, cnt, res);
        cnt--;
        if(cnt == 0){
            res = root->val;
        }
        dfs(root->left, cnt, res);
    }
};

时间复杂度O(N)，空间复杂度O(N)。

0 赞同 0 条回复

Jerry 普通 2024年12月2日下午10:40

class Solution {
public:
    vector<int> res;
    int findTargetNode(TreeNode* root, int cnt) {
        findTargetNodehelper(root);
        return res[cnt-1];
    }
    void findTargetNodehelper(TreeNode* root){
        if(!root) return;
        findTargetNodehelper(root->right);
        res.push_back(root->val);
        findTargetNodehelper(root->left);
        return;
    }
};

时间o(n)
空间o(n)

0 赞同 0 条回复

lQl 永久会员 2024年12月2日下午8:03

中序遍历,但是没用递归

class Solution {
    public int findTargetNode(TreeNode root, int cnt) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> s = new Stack<>();
        TreeNode cur = root;

        while(cur!=null||!s.isEmpty()){
            while(cur!=null){
                s.push(cur);
                cur = cur.left;
            }
            cur = s.pop();
            result.add(cur.val);
            cur = cur.right;
        }

        return result.get(result.size()-cnt);
    }
}

0 赞同 0 条回复

秋山丽奈普通 2024年12月2日下午7:04

思路：中序遍历记录节点

class Solution {

    List<Integer> ans = new ArrayList<>();

    public int findTargetNode(TreeNode root, int cnt) {
        // 使用中序遍历 保存
        dfs(root);

        return ans.get(ans.size()-cnt); 
    }

    void dfs(TreeNode node){
        if(node == null){
            return;
        }

        dfs(node.left);
        ans.add(node.val);
        dfs(node.right);
    }
}

0 赞同 0 条回复

黑键〰普通 2024年12月2日下午3:15

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} cnt
 * @return {number}
 */
var findTargetNode = function(root, cnt) {
    // 二叉搜索树特性，中序遍历可以拿到第k小的数值，左根右
    // 因此想拿第k大的数值则换成，右根左
    let res = null
    const find = (root) => {
        if(root == null || cnt < 0) return
        // 右根左打印
        find(root.right)
        cnt-- // 每打印一次右边的，即打印一次相对更大的值，cnt就减一
        if(cnt == 0) res = root.val
        find(root.left)
    }
    find(root, cnt)
    return res
};

思路：中序遍历，换成右根左的顺序打印。注意可以在记数为0后剪枝

0 赞同 0 条回复

遇事不决睡大觉普通 2024年12月1日下午3:03

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
int res, cnt;

public int findTargetNode(TreeNode root, int cnt) {
    this.cnt = cnt;
    dfs(root);
    return res;
}

void dfs(TreeNode root) {
    if (root == null)
        return;
    dfs(root.right);
    if (cnt == 0)
        return;
    if (--cnt == 0)
        res = root.val;
    dfs(root.left);
}

}//倒着来就行

0 赞同 0 条回复

月下足迹普通 2024年12月1日下午1:19

public class Solution {
private int result; // 存储目标节点值
private int count; // 记录已访问的节点数

public int findTargetNode(TreeNode root, int cnt) {
    count = 0;     // 初始化已访问节点数为 0
    result = -1;   // 初始化结果为 -1（假设节点值均为非负）
    reverseInorder(root, cnt);
    return result;
}

// 逆序中序遍历：右 -> 根 -> 左
private void reverseInorder(TreeNode node, int cnt) {
    if (node == null) return;

    // 先递归遍历右子树
    reverseInorder(node.right, cnt);

    // 访问当前节点
    count++;
    if (count == cnt) { // 找到目标节点
        result = node.val;
        return;         // 提前退出递归
    }

    // 再递归遍历左子树
    reverseInorder(node.left, cnt);
}

}

0 赞同 0 条回复

jaron 普通 2024年12月1日下午12:34

在中序遍历的递归版本中进行剪枝

class Solution {
    int k;
    int res;
    public int findTargetNode(TreeNode root, int cnt) {
        k = cnt;
        f(root);
        return res;
    }

    public void f(TreeNode root){
        if(root == null || k <= 0){
            return;
        }
        // 从大到小，所以先右节点
        f(root.right);
        k --;
        if(k == 0){
            res = root.val;
        }
        f(root.left);
    }
}

0 赞同 0 条回复

Xiang. 永久会员 2024年12月1日上午11:18

思路：结合二叉搜素树的性质，中序遍历结果从左到右依次递增，所以第cnt大的数即为中序遍历结果的倒数第cnt个数。
class Solution {
    List<Integer> res=new ArrayList();
    public int findTargetNode(TreeNode root, int cnt) {
        innoder_iteration(root,res);
        return res.get(res.size()-cnt);
    }
    public void innoder_recursion(TreeNode root,List<Integer> res){
        if(root==null) return ;
        innoder_recursion(root.left,res);
        res.add(root.val);
        innoder_recursion(root.right,res);
    } 
    public void innoder_iteration(TreeNode root,List<Integer> res){
        if(root==null) return;
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        while(!stack.empty()||cur!=null){
            if(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }else{
                TreeNode tmp=stack.pop();
                cur=tmp;
                res.add(tmp.val);
                cur=cur.right;
            }
        }
    }
}
时间复杂度：O（n）
空间复杂度：O（n）

0 赞同 0 条回复

Kisara 普通 2024年11月30日下午10:25

花了4ms的暴力方法，遍历所有节点存入列表然后排序，最后取出。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<Integer> list=new ArrayList<>();
    public int findTargetNode(TreeNode root, int cnt) {
       solve(root);
       Collections.sort(list);
       return list.get(list.size()-cnt);
    }

    void solve(TreeNode root){
        if(root==null) return;

        list.add(root.val);
        solve(root.right);
        solve(root.left);

    }
}

On On
看了题解的思路写的法二

 class Solution {
    int res,cnt;
    public int findTargetNode(TreeNode root, int cnt) {
      this.cnt=cnt;
      solve(root);
      return res;
    }

    void solve(TreeNode root){
       if(root==null) return;

       solve(root.right);
       if(cnt==0) return;
       if(--cnt==0) res=root.val;

       solve(root.left);
    }
}

on on

0 赞同 0 条回复

Renasc 普通 2024年11月30日下午9:39

时间复杂度O(n)，空间复杂度O(h)

class Solution {
    // 设置全局变量
    int res, cnt;
    public int findTargetNode(TreeNode root, int cnt) {
        this.cnt = cnt;
        // 深度优先遍历
        dfs(root);
        return res;
    }

    public void dfs(TreeNode root) {
        if (root == null || cnt <= 0) return;

        // 递归遍历, 中序遍历逆序
        dfs(root.right);
        if (--cnt == 0) res = root.val;
        dfs(root.left);
    }
}

0 赞同 0 条回复

迢迢星野普通 2024年11月30日下午8:57

class Solution {
    /**
     * 题意解读：获取二叉搜索树中的第 cnt 大的员工编号。
     *          二叉搜索树的中序遍历是升序的，求第 cnt 大的员工编号：中序遍历倒序后，第 cnt 个的值就是所求值。
     * @param root
     * @param cnt
     * @return
     */
    public int findTargetNode(TreeNode root, int cnt) {
        // 中序遍历
        traverse(root, cnt);
        return res;
    }

    int res = 0;
    // 遍历的节点个数
    int count = 0;

    private void traverse(TreeNode node, int cnt) {
        if (node == null) {
            return;
        }

        traverse(node.right, cnt);
        count++;

        if (count == cnt) {
            res = node.val;
            // return;
        }
        traverse(node.left, cnt);
    }
}

思路：二叉搜索树的中序遍历结果是升序的，“所求的第 cnt 大的节点”可以转换为“中序遍历倒序的第 cnt 个节点”。而二叉搜索树的中序遍历倒序的递归遍历方式：右-根-左。
时间复杂度：O(n)
空间复杂度：O(n)

0 赞同 0 条回复

YULONG 永久会员 2024年11月30日下午8:45

/**
 解题思路：
 根据性质，二叉搜索树中序遍历结果为升序数组，遍历顺序调整为right->root->left即为降序
 套用中序遍历模版即可
 时间复杂度O(N)
 空间复杂度O(N)
 */
class Solution {
    public int findTargetNode(TreeNode root, int cnt) {


        Deque<TreeNode> st = new ArrayDeque<>();
        TreeNode p = root;
        while (!st.isEmpty() || p != null){
            while (p != null){
                st.add(p);
                p = p.right;
            }
            TreeNode cur = st.pollLast();
            if (cnt == 1){
                return cur.val;
            }
            cnt--;
            p = cur.left;
        }
        return -1;



    }
}

0 赞同 0 条回复

苯庸普通 2024年11月30日下午7:55

class Solution {// 右中左
int res = 0, cnt = 0;
public int findTargetNode(TreeNode root, int k) {
dfs(root, k);
return res;
}

void dfs(TreeNode root, int k){
    if(root == null) return;
    dfs(root.right, k);
    if(++cnt == k){
        res = root.val;
    }
    dfs(root.left, k);
}

}
时间：O（n）
空间：O（n）

0 赞同 0 条回复

【二叉树专题】剑指 Offer 54. 二叉搜索树的第k大节点

共以下 20 个回答

LCR 174. 寻找二叉搜索树中的目标节点

# 回答此问题取消回复

【二叉树专题】剑指 Offer 54. 二叉搜索树的第k大节点

共以下 20 个回答

LCR 174. 寻找二叉搜索树中的目标节点

# 回答此问题 取消回复

# 回答此问题取消回复