YOLO 普通 2024年3月31日上午12:26

/* 给定一棵二叉搜索树，请找出其中第 k 大的节点的值。 */
class Solution {
    int target = 0;
    int cnt;

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

    void rrl(TreeNode root) {
        if (root == null || cnt <= 0) {
            return;
        }
        rrl(root.right);
        cnt--;
        if (cnt == 0) {
            target = root.val;
        }
        rrl(root.left);
    }
}

0 赞同 0 条回复

kfaebot 普通 2024年3月22日下午4:47

/**
 * 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 {
public:
    vector<int> middle;
    //中序遍历
    void inorder(TreeNode* root){
        if(root==nullptr){
            return;
        }
        inorder(root->left);
        middle.push_back(root->val);
        inorder(root->right);
    }
    int findTargetNode(TreeNode* root, int cnt) {
        inorder(root);
        return middle[middle.size()-cnt];
    }
};

0 赞同 0 条回复

NULL 普通 2024年3月21日上午10:00

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)return;
    if(--cnt == 0)res = root.val;
    dfs(root.left);
}

}

0 赞同 0 条回复

紫芝普通 2024年3月15日下午10:59

思路：中序遍历的倒序，获取第cnt个遍历的节点的值即为第k大节点

var res, cnt_a int
func dfs(root *TreeNode) {
    if root == nil { return } 
    dfs(root.Right)
    if cnt_a == 0 { return }
    cnt_a--
    if cnt_a == 0 { res = root.Val }
    dfs(root.Left)
}
func findTargetNode(root *TreeNode, cnt int) int {
    cnt_a = cnt
    dfs(root)
    return res
}

0 赞同 0 条回复

叫不醒装睡的人普通 2024年3月15日下午7:03

class Solution {
    // 二叉搜索树特性，右子大于根大于左子
    int res, cnt;

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

    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.right);
        if (cnt == 0) {
            return;
        }
        if (--cnt == 0) {
            res = root.val;
        }
        dfs(root.left);
    }
    // 时间复杂度为 O(n)
    // 空间复杂度为 O(n)
}

0 赞同 0 条回复

mpweixin用户普通 2024年3月14日下午10:18

java
class Solution {
LinkedList list = new LinkedList<>();
public int findTargetNode(TreeNode root, int k) {
dfs(root);
return list.get(list.size() – k);
}

void dfs(TreeNode root){
    if(root == null){
        return ;
    }
    dfs(root.left);
    list.add(root.val);
    dfs(root.right);
}

}
提交

0 赞同 0 条回复

一个达不刘普通 2024年3月13日下午3:27

class Solution {
public:
int findTargetNode(TreeNode* root, int cnt) {
this->cnt = cnt;
dfs(root);
return res;
}
private:
int res, cnt;
void dfs(TreeNode* root) {//倒序，中序遍历，递减数列
if(root nullptr) return;
dfs(root->right);
if(cnt 0) return;
if(–cnt 0) res = root->val;
dfs(root->left);
}
};

0 赞同 0 条回复

神经蛙普通 2024年3月13日上午12:08

class Solution {
public:
int findTargetNode(TreeNode* root, int cnt) {
if(root nullptr) return 0;
this->cnt = cnt;
f(root);

    return res;
}
void f(TreeNode *root)
{
    if(root == nullptr) return;
    f(root->right);
     //根节点
     if(--cnt == 0) res = root->val;
     f(root->left);
}

private:
int res;
int cnt；
};
思路：二叉搜索树的中序遍历为（左中右）为递减序列，那么（右中左）为递增序列
时间、空间复杂度O(n)

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年3月12日下午10:34

class Solution {
    int k=0;
    int target=0;
    public int findTargetNode(TreeNode root, int cnt) {
        this.k=cnt;
        f(root);
        return target;
    }

    public void f(TreeNode root){

        if(root==null || k<0) return;

        f(root.right);

        k--;
        if(k==0){
            target=root.val;
            return;
        }

        f(root.left);
    }
}

时间复杂度：最差为 O(n)，平均为 logn
空间复杂度：最差为 O(n)，平均为 logn

0 赞同 0 条回复

Jimmy 普通 2024年3月12日下午10:30

//另一种方法：
/**
 * 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 {
public:
    int k;
    int target;
    int findTargetNode(TreeNode* root, int cnt) {
        k = cnt;
        travesal(root);
        return target;
    }

    void travesal(TreeNode* root){
        if(root == nullptr || k<0)return;
        travesal(root->right);
        k--;
        if(k == 0) target = root->val;
        travesal(root->left);
    }
};

0 赞同 0 条回复

东普通 2024年3月12日下午9:16

/**
 * 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) {
        dfs(root);
//使用list来存储
        Collections.sort(list);
        return list.get(list.size() - cnt);
    }
    void dfs(TreeNode root) {
        if (root == null) return ;
        dfs(root.left);
        list.add(root.val);
        dfs(root.right);
    }
}

0 赞同 0 条回复

进取普通 2024年3月12日下午8:36

class Solution {
public:
void dfs(vector& v, TreeNode* root){
if (root nullptr) return ;
dfs(v, root->left);
v.push_back(root->val);
dfs(v, root->right);
}
int findTargetNode(TreeNode* root, int cnt) {
vector v;
dfs(v, root);
return v[v.size() – cnt];
}
};注意，二叉搜索树的节点关系。左<根<右—符合中序遍历，返回中序遍历的倒数第几个节点就是

0 赞同 0 条回复

RunAsOne 普通 2024年3月12日下午4:28

第二次打卡二叉搜索树

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def findTargetNode(self, root, cnt):
        """
        :type root: Optional[TreeNode]
        :type cnt: int
        :rtype: int
        """
        self.target = 0
        def right_left(root):
            if not root:
                return
            right_left(root.right)
            self.cnt-=1
            if self.cnt == 0:
                self.target = root.val
            right_left(root.left)
        self.cnt = cnt
        right_left(root)
        return self.target

0 赞同 0 条回复

mpweixin用户普通 2024年3月12日下午4:12

int res,cnt;
public int findTargetNode(TreeNode root, int cnt) {
this.cnt=cnt;
dfs(root);
return res;
}
void dfs(TreeNode root){
if(rootnull) return;
dfs(root.right);
if(cnt0) return;
if(–cnt0) res=root.val;
dfs(root.left);
}
思路：二叉搜索树的中序遍历是递增的反过来就是递减
找到第n个返回即可

0 赞同 0 条回复

方铎码农普通 2024年3月12日下午3:41

二叉搜索树本质上是中序遍历建构的结果，中序遍历前面小，后面大，只需要按照中序遍历的方向反过来就可以了。

辅助栈反推法

//二叉搜索树需要中序遍历，遍历出有序的序列（左 -> 根 -> 右，从小到大）
class Solution {

    public int findTargetNode(TreeNode root, int cnt) {
        int k = cnt;
        int target = 0;
        if(root == null) return target;
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        while(!stack.isEmpty() || root != null){
            if(root != null){
                stack.push(root);
                root = root.right;
            } else {
                root = stack.pop();
                k--;
                if(k == 0) target = root.val;
                root = root.left;
            }
        }
        return target;
    }
}

时间复杂度$O(n)$(理论，实际上由于栈的内部过程是要比递归法慢的），空间复杂度$O(n)$

递归法

//二叉搜索树需要中序遍历，遍历出有序的序列（左 -> 根 -> 右，从小到大）
class Solution {
    int target;
    int k;

    public int findTargetNode(TreeNode root, int cnt) {
        this.k = cnt;
        rightRootLeft(root);
        return target;
    }

    private void rightRootLeft(TreeNode root){
        if(root == null || k <= 0) return;
        rightRootLeft(root.right);
        k--;
        if(k == 0){
            target = root.val;
        }
        rightRootLeft(root.left);
    } 
}

时间复杂度$O(n)$，额外空间复杂度$O(n)$（递归栈）

0 赞同 0 条回复

机电皮怪永久会员 2024年3月12日上午10:35

时间复杂度O(n)
空间复杂度O(n)
中序遍历之后是一个有序的从小到大的数组，然后数组大小-cnt即可

“`C++
class Solution {
public:
int findTargetNode(TreeNode* root, int cnt) {
if(root == nullptr)
{
return -1;
}
//中序遍历
stack sub;
vector result;
TreeNode* cur = root;
do
{
while(cur != nullptr)
{
sub.push(cur);
cur = cur->left;
}
//出栈时节点存入数组容器
if(sub.empty() == false)
{
cur = sub.top();
result.push_back(cur->val);
cur = cur->right;
sub.pop();
}
}while(cur != nullptr || sub.empty() == false);

    return result[result.size() - cnt];
}

};

“`

0 赞同 0 条回复

Yuki 永久会员 2024年3月12日上午10:08

BST性质
https://leetcode.cn/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/solutions/2681846/xun-zhao-er-cha-sou-suo-shu-zhong-de-mu-5g1eb

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月12日上午8:17

打卡

class Solution {
public:
    int findTargetNode(TreeNode* root, int cnt) {
        int res = 0;
        if(!root) return res;
        stack<TreeNode*> stk;
        while(!stk.empty() || root) {
            if(root) {
                stk.push(root);
                root = root->right;
            } else {
                root = stk.top(); stk.pop();
                if(--cnt == 0) res = root->val;
                root = root->left;
            }
        }
        return res;
    }
};

0 赞同 0 条回复

Yox 普通 2024年3月12日上午6:14

Definition for a binary tree node.

class TreeNode:

def init(self, val=0, left=None, right=None):

self.val = val

self.left = left

self.right = right

class Solution:
def findTargetNode(self, root: Optional[TreeNode], cnt: int) -> int:
def dfs(root):
if not root:return
dfs(root.right)
self.cnt -= 1
if self.cnt 0: self.res = root.val
dfs(root.left)

    self.cnt = cnt
    dfs(root)
    return self.res

双 on

0 赞同 0 条回复

南梁陈庆之普通 2024年3月12日上午12:55

使用递归，使用中序遍历后，二叉树的数据就是顺序数据。然后使用栈保存，取出倒数cnt的数据

/**
 * 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 {
    Stack<Integer> stack = new Stack<>();
    public int findTargetNode(TreeNode root, int cnt) {
        midPrint(root);
        if (cnt > stack.size()) {
            return -1;
        }

        for (int i = 0; i < cnt - 1; i++) {
            stack.pop();
        }
        return stack.pop();

    }

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

        midPrint(node.left);
        stack.add(node.val);
        midPrint(node.right);
    }
}

0 赞同 0 条回复

MARS 普通 2024年3月11日下午11:55

day10第一题

function findTargetNode(root: TreeNode | null, cnt: number): number {
    let res = [] //收集信息
    dfs(root)
    return res[cnt-1]
    function dfs(root: TreeNode | null){
        if(root ==null) return
        if(root.right){
            dfs(root.right)
        }
        res.push(root.val)
        if(root.left){
            dfs(root.left)
        }
    }
};

0 赞同 0 条回复

云无深雁影普通 2024年3月11日下午10:44

//方法1 递归
class Solution {
HashMap<Integer,Integer> map = new HashMap<>();
public int findTargetNode(TreeNode root, int cnt) {
if(cnt count(root.right) + 1){
return root.val;
}
else if(cnt > count(root.right) + 1){
return findTargetNode(root.left,cnt – count(root.right) – 1);
}
else
return findTargetNode(root.right,cnt);

}
private int count(TreeNode node){
    if(node == null)
        return 0;
    if(map.containsKey(node.val))
        return map.get(node.val);
    int count = count(node.left) + count(node.right) + 1;
    map.put(node.val,count);
    return count; 
}

}
//方法2 类中序遍历
class Solution {
public int findTargetNode(TreeNode root, int cnt) {
//中序遍历
int count = 0;
Stack stack = new Stack<>();
while(root!=null || !stack.empty()){
while(root != null){
stack.push(root);
root = root.right;
}
root = stack.pop();
count++;
if(count cnt) return root.val;
root = root.left;
if(count cnt) return root.val;

    }
    return -1;
}

}

0 赞同 0 条回复

Raphtalia. 普通 2024年3月11日下午10:15

/**
* 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 {
public:
int findTargetNode(TreeNode root, int cnt) {
if(root nullptr) return -1;
this->cnt = cnt;
dfs(root);
return res;
}
private:
int cnt = 0, res = 0;
void dfs(TreeNode* root){
if(!root) return;
dfs(root->right);
if(cnt 0) return;
else {
–cnt;
res = root->val;
}
dfs(root->left);
}
};
时间复杂度O（n），最坏空间复杂度O（n）

0 赞同 0 条回复

言之命至普通 2024年3月11日下午10:06

class Solution {
        int k = 0;
    int target = 0;
    public int findTargetNode(TreeNode root, int cnt) {
   // 中序遍历：有序的序列 左 根 右 从小到大排序的
        //                   右 根 左 从大到小的排序
        this.k = cnt;//k=0时的值即所求
        right_root_left(root);
        return target;
    }

     void right_root_left(TreeNode root){
        if(root == null || k <= 0) return;

        right_root_left(root.right);
        // 打印当前根节点
        k--;
        if(k == 0){
            target = root.val;
        }
        right_root_left(root.left);

    }
}

0 赞同 0 条回复

Free 普通 2024年3月11日下午9:15

/**
 * 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 
{
    int res, count;
public:
    int findTargetNode(TreeNode* root, int cnt) 
    {
        count = cnt;
        dfs(root);
        return res;
    }

    void dfs(TreeNode* root)
    {
        if(root == nullptr)
            return;
        if(count < 0)
            return;
        dfs(root->right);
        if(--count == 0)
            res = root->val;
        dfs(root->left);
    }
};

时空复杂度O(N)

0 赞同 0 条回复

是hua不是pua 普通 2024年3月11日下午9:11

“`java
class Solution {
public Integer count = 0;
public Integer result = null;
public Boolean isFound = false;
public int findTargetNode(TreeNode root, int cnt) {
this.count = cnt;
middleSearch(root);
return result;
}

public void middleSearch(TreeNode root){
    if(root == null || isFound){
        return;
    }
    middleSearch(root.right);
    count--;
    if(count == 0){
        result = root.val;
        isFound = true;
        return;
    }
    middleSearch(root.left);
}

}

“` 左中右遍历是递增，右中左是递减。

0 赞同 0 条回复

heathhou 普通 2024年3月11日下午8:09

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

    }

    // 递归函数：  右——中——左 递归二叉树
    void right_root_left(TreeNode* root){
        if(root == nullptr || k < 0 ){
            return;
        }
        right_root_left(root->right);
        --k;
        if(k == 0){
            ans = root->val;
            return;
        }

        right_root_left(root->left);
    }
};

0 赞同 0 条回复

王位詮釋普通 2024年3月11日下午7:53

class Solution {
    public int findTargetNode(TreeNode root, int cnt) {
        List<Integer> result = new ArrayList<>();
        inorder(result,root);
        return result.get(result.size()-cnt);
    }
    public void inorder(List<Integer> result,TreeNode root){
        if(root==null){
            return;
        }
        inorder(result,root.left);
        result.add(root.val);
        inorder(result,root.right);
    }
}
思路：二叉搜索树的左子树节点val都比根节点小，右子树节点都比根节点val大，因此二叉搜索树的中序遍历序列刚好就是从小到大排列的，所以先获取到中序遍历的结果，然后再返回倒数第cnt的值
时间复杂度：O(n)，遍历了树的所有节点
空间复杂度：O(n)，用了一个额外的动态数组来存储中序遍历的结果。

0 赞同 0 条回复

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

共以下 28 个回答

辅助栈反推法

递归法

Definition for a binary tree node.

class TreeNode:

def init(self, val=0, left=None, right=None):

self.val = val

self.left = left

self.right = right

# 回答此问题取消回复

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

共以下 28 个回答

辅助栈反推法

递归法

Definition for a binary tree node.

class TreeNode:

def init(self, val=0, left=None, right=None):

self.val = val

self.left = left

self.right = right

# 回答此问题 取消回复

# 回答此问题取消回复