首页 > 试题广场 >

找到二叉树中的最大搜索二叉子树

[编程题]找到二叉树中的最大搜索二叉子树
  • 热度指数:2997 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给定一颗二叉树,已知其中所有节点的值都不一样,找到含有节点最多的搜索二叉子树,输出该子树总节点的数量。
搜索二叉树是指对于二叉树的任何一个节点,都大于其左子树中的全部节点,但是小于其右子树中的全部节点。

输入描述:
第一行输入两个整数 n 和 root,n 表示二叉树的总节点个数,root 表示二叉树的根节点。

以下 n 行每行三个整数 fa,lch,rch,表示 fa 的左儿子为 lch,右儿子为 rch。(如果 lch 为 0 则表示 fa 没有左儿子,rch同理)

ps:节点的编号就是节点的值。


输出描述:

示例1

输入

3 2
2 1 3
1 0 0
3 0 0

输出

3
树型DP,使用二叉树的递归套路,根据是否要将当前结点纳入搜索二叉树划分可能性。需要向左子树和右子树要五个信息:
  1. 子树的最大二叉搜索树的根结点;
  2. 子树的最大二叉搜索树的节点数量;
  3. 子树是否是二叉搜索树;
  4. 子树的节点最小值;
  5. 子树的节点最大值。
将左右子树的以上五个信息整合为当前节点的五个信息,以供更上层的节点使用。最终根节点得到的最大二叉搜索树节点数量就是我们要求的答案。整个过程其实就是二叉树的后续遍历,中间的比较过程都是O(1)的时间复杂度,算法的整体时间复杂度为O(N)。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashMap;

class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val) {
        this.val = val;
    }
}

class Info {
    public TreeNode maxBSTHead;
    public int maxBSTSize;
    public boolean isBST;
    public int min;
    public int max;
    public Info(TreeNode maxBSTHead, int maxBSTSize, boolean isBST, int min, int max) {
        this.maxBSTHead = maxBSTHead;
        this.maxBSTSize = maxBSTSize;
        this.isBST = isBST;
        this.min = min;
        this.max = max;
    }
}

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        HashMap<Integer, TreeNode> map = new HashMap<>();
        String[] params = br.readLine().split(" ");
        int n = Integer.parseInt(params[0]), rootVal = Integer.parseInt(params[1]);
        // 构建二叉树
        TreeNode root = new TreeNode(rootVal);
        map.put(rootVal, root);
        for(int i = 0; i < n; i++){
            params = br.readLine().split(" ");
            int nodeVal = Integer.parseInt(params[0]);
            int leftVal = Integer.parseInt(params[1]);
            int rightVal = Integer.parseInt(params[2]);
            TreeNode node = map.get(nodeVal);
            if(leftVal != 0) {
                node.left = new TreeNode(leftVal);
                map.put(leftVal, node.left);
            }
            if(rightVal != 0) {
                node.right = new TreeNode(rightVal);
                map.put(rightVal, node.right);
            }
        }
        // 求解
        System.out.println(process(root).maxBSTSize);
    }
    
    private static Info process(TreeNode node) {
        if(node == null) return null;
        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right);
        TreeNode maxBSTHead = null;
        int maxBSTSize = 0;
        int max = node.val;
        int min = node.val;
        // 最值在左右信息不为空的时候需要比较更新
        if(leftInfo != null){
            maxBSTHead = leftInfo.maxBSTHead;
            maxBSTSize = leftInfo.maxBSTSize;
            max = Math.max(max, leftInfo.max);
            min = Math.min(min, leftInfo.min);
        }
        if(rightInfo != null){
            if(rightInfo.maxBSTSize > maxBSTSize){
                maxBSTHead = rightInfo.maxBSTHead;
                maxBSTSize = rightInfo.maxBSTSize;
            }
            max = Math.max(max, rightInfo.max);
            min = Math.min(min, rightInfo.min);
        }
        boolean isBST = false;
        // 左右子树都是BST且能够和当前节点连起来时,能够形成一个以当前节点为根的更大的BST
        if((leftInfo == null || (leftInfo.isBST && leftInfo.max < node.val)) && (rightInfo == null || (rightInfo.isBST && rightInfo.min > node.val))){
            isBST = true;
            maxBSTHead = node;
            maxBSTSize = (leftInfo != null? leftInfo.maxBSTSize: 0) + (rightInfo != null? rightInfo.maxBSTSize: 0) + 1;
        }
        return new Info(maxBSTHead, maxBSTSize, isBST, min, max);
    }
}

发表于 2021-11-26 18:47:35 回复(0)

很好理解,但是时间复杂度比较高

import java.util.HashMap;
import java.util.Scanner;

/**
 * @Author fgf
 * @create 2020/3/10 22:12
 * 找到二叉树中的最大搜索二叉之树
 */
class Node {
    public int value;
    public Node left;
    public Node right;
    public Node(int data){
        this.value = data;
    }
}

public class Main {
    private static Node bstNode = null;
    private static int max = Integer.MIN_VALUE;
    private static int pre = Integer.MIN_VALUE;

    public static void getMaxBST(Node root){
        if(root == null)
            return;
        pre = Integer.MIN_VALUE;
        if(isBST(root)){
            int nodesNum = getNodesNum(root);
            if(nodesNum > max){
                max = nodesNum;
                bstNode = root;
            }
        }
        getMaxBST(root.left);
        getMaxBST(root.right);
    }
    //获得二叉树节点个数
    public static int getNodesNum(Node root){
        if(root == null)
            return 0;
        return 1 + getNodesNum(root.left) + getNodesNum(root.right);
    }
    //判断是否是一颗搜索二叉树 中序遍历 左中右
    public static boolean isBST(Node root){
        if(root == null)
            return true;
        boolean flagLeft = isBST(root.left);
        if(pre >= root.value)
            return false;
        pre = root.value;
        if(flagLeft == false)
            return false;
        else
            return isBST(root.right);
    }


    public static void main(String[] args) {
/**
13 6
6 1 12
1 -1 3
12 10 13
-1 0 0
3 0 0
10 4 14
13 20 16
4 2 5
14 11 15
2 0 0
5 0 0
11 0 0
15 0 0
 */
        Scanner scanner = new Scanner(System.in);
        int count = scanner.nextInt();
        Node root = new Node(scanner.nextInt());
        HashMap<Integer, Node> hashMap = new HashMap<>();
        hashMap.put(root.value, root);
        int[][] nodes = new int[count][3];
        for(int i=0; i<count; i++){
            for(int j=0; j<3; j++){
                int v = scanner.nextInt();
                if(v != 0)
                    hashMap.put(v, new Node(v));
                nodes[i][j] = v;
            }
        }
        for(int i=0; i<count; i++){
            int[] arr = nodes[i];
            Node fakeRoot = hashMap.get(arr[0]);
            if(arr[1] != 0)
                fakeRoot.left = hashMap.get(arr[1]);
            if(arr[2] != 0)
                fakeRoot.right = hashMap.get(arr[2]);
        }
        root = hashMap.get(root.value);
        getMaxBST(root);
        System.out.println(max);
//        System.out.println(bstNode.value);
//        System.out.println(isBST(root));
    }
}
发表于 2020-03-10 23:03:05 回复(0)
//参考左神的📕
#include<iostream>
#include<climits>
using namespace std;
//树节点
struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
};
树dp的信息
struct BSTtype{
    TreeNode* pBSTHead;
    int BSTsize;
    int valmax;
    int valmin;
    BSTtype(TreeNode* _pBSTHead,int _BSTsize,int _valmax,int _valmin){
        pBSTHead = _pBSTHead;
        BSTsize = _BSTsize;
        valmax = _valmax;
        valmin = _valmin;
    }
};
//递归过程
BSTtype process(TreeNode* pRoot){
    if(pRoot==nullptr){
        return BSTtype(nullptr,0,INT_MIN,INT_MAX);
    }
    BSTtype lnode =process(pRoot->left);
    BSTtype rnode =process(pRoot->right);
    int curmax = max(pRoot->val,max(lnode.valmax,rnode.valmax));
    int curmin = min(pRoot->val,min(lnode.valmin,rnode.valmin));
    int cursize =max(lnode.BSTsize,rnode.BSTsize);
    TreeNode* pCurHead = lnode.BSTsize>rnode.BSTsize?lnode.pBSTHead:rnode.pBSTHead;
    if(pRoot->left == lnode.pBSTHead && pRoot->right==rnode.pBSTHead && lnode.valmax < pRoot->val&& rnode.valmin > pRoot->val){
        pCurHead = pRoot;
        cursize = lnode.BSTsize+rnode.BSTsize+1;
    }
    return BSTtype(pCurHead,cursize,curmax,curmin);
}
//创建树
void createTree(TreeNode* pRoot,int& n){
    if(n==0){
        return;
    }
    int rootval,leftval,rightval;
    cin>>rootval>>leftval>>rightval;
    if(leftval!=0){
        TreeNode* leftnode = new TreeNode;
        leftnode->val = leftval;
        leftnode->left =leftnode->right=nullptr;
        pRoot->left = leftnode;
        createTree(leftnode,--n);
        
    }
    if(rightval!=0){
        TreeNode* rightnode = new TreeNode;
        rightnode->val = rightval;
        rightnode->left =rightnode->right=nullptr;
        pRoot->right = rightnode;
        createTree(rightnode,--n);
    }
}
int main(){
    int n,rootval;
    cin>>n>>rootval;
    TreeNode* pRoot = new TreeNode;
    pRoot->val = rootval;
    pRoot->left = pRoot->right = nullptr;
    TreeNode* pCurrnode =pRoot;
    while(n--){
        createTree(pCurrnode,n);
    }
    BSTtype res = process(pCurrnode);
    cout<<res.BSTsize<<endl;
    return 0;
}
发表于 2020-07-27 20:02:11 回复(0)
#include<bits/stdc++.h>
using namespace std;
struct ReturnType{
    int maxBSTHead;
    int maxBSTSize;
    int MIN;
    int MAX;
    ReturnType(int root,int size,int Min,int Max):maxBSTHead(root),maxBSTSize(si***(Min),MAX(Max){}
};
ReturnType process(int root,int* lc,int* rc)
{
    // base case 注意最大最小值的赋值
    if(!root) return ReturnType(0,0,INT_MAX,INT_MIN);
    // 搜集到左右子树的信息
    ReturnType ldata = process(lc[root],lc,rc);
    ReturnType rdata = process(rc[root],lc,rc);
    // 整合
    // 以当前结点为根的最大值与最小值
    int max_ = max(root,max(ldata.MAX,rdata.MAX));
    int min_ = min(root,min(ldata.MIN,rdata.MIN));
    // 最大搜索二叉子树来源于左子树或右子树
    int curMaxBSTHead = ldata.maxBSTSize>rdata.maxBSTSize ? ldata.maxBSTHead:rdata.maxBSTHead;
    int curMaxBSTSize = max(ldata.maxBSTSize,rdata.maxBSTSize);
    // 要把根节点加入进去的情况
    if(ldata.maxBSTHead == lc[root] && rdata.maxBSTHead == rc[root] && root>ldata.MAX && root<rdata.MIN)
    {
        curMaxBSTHead = root;
        curMaxBSTSize = 1 + ldata.maxBSTSize + rdata.maxBSTSize;
    }
    return ReturnType(curMaxBSTHead,curMaxBSTSi***_,max_);
}
int main()
{
    int n,root;
    cin>>n>>root;
    int* lc = new int[n+1];
    int* rc = new int[n+1];
    int p;
    for(int i=0;i<n;++i)
    {
        cin>>p;
        cin>>lc[p]>>rc[p];
    }
    int ans = process(root,lc,rc).maxBSTSize;
    cout<<ans<<endl;

    return 0;
}
编辑于 2020-02-05 11:10:25 回复(0)
import java.lang.Math;
import java.util.Scanner;
import java.util.HashMap;

class Info{
    boolean flag = true;
    int nodesNum = 0;
}

class Node{
    int value;
    Node left;
    Node right;
    
    public Node(int value){
        this.value = value;
    }
}

public class Main{
    public static void main(String[] args){
        HashMap<Integer, Node> map = new HashMap<>();
        Scanner sc = new Scanner(System.in);
        String firstLine = sc.nextLine();
        String[] params = firstLine.split(" ");
        int n = Integer.valueOf(params[0]);
        int rootVal = Integer.valueOf(params[1]);
        Node root = new Node(rootVal);
        map.put(rootVal, root);
        
        //构建二叉树
        for(int i=0; i<n; i++){
            String line = sc.nextLine();
            String[] str = line.split(" ");
            int faVal = Integer.valueOf(str[0]);
            int lchVal = Integer.valueOf(str[1]);
            int rchVal = Integer.valueOf(str[2]);
            
            Node curNode = map.get(faVal);
            if(lchVal != 0){
                curNode.left = new Node(lchVal);
                map.put(lchVal, curNode.left);
            }
            if(rchVal != 0){
                curNode.right = new Node(rchVal);
                map.put(rchVal, curNode.right);
            }
        }
        
        Info info = process(root);
        System.out.println(info.nodesNum);
        
    }
    
    
    public static Info process(Node node){
        Info curInfo = new Info();
        
        if(node == null){
            return curInfo;
        }
        
        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right);
        
        if(((leftInfo.flag && rightInfo.flag) != true) ||
          (node.left != null && getTreeMaxValue(node.left)>node.value) ||
          (node.right != null && getTreeMinValue(node.right)<node.value)){
            curInfo.flag = false;
            curInfo.nodesNum = Math.max(leftInfo.nodesNum, rightInfo.nodesNum);            
            return curInfo;
        }
        
        curInfo.nodesNum = leftInfo.nodesNum + rightInfo.nodesNum + 1;
        
        return curInfo;
    }
    
    
    public static int getTreeMaxValue(Node node){
        while(node.right != null){
            node = node.right;
        }
        return node.value;
    }
    
    public static int getTreeMinValue(Node node){
        while(node.left != null){
            node = node.left;
        }
        return node.value;
    }
    
}

import java.lang.Math;
import java.util.Scanner;
import java.util.HashMap;

class Info{
    boolean flag = true;
    int nodesNum = 0;
    int max;
    int min;
}

class Node{
    int value;
    Node left;
    Node right;
    
    public Node(int value){
        this.value = value;
    }
}

public class Main{
    public static void main(String[] args){
        HashMap<Integer, Node> map = new HashMap<>();
        Scanner sc = new Scanner(System.in);
        String firstLine = sc.nextLine();
        String[] params = firstLine.split(" ");
        int n = Integer.valueOf(params[0]);
        int rootVal = Integer.valueOf(params[1]);
        Node root = new Node(rootVal);
        map.put(rootVal, root);
        
        //构建二叉树
        for(int i=0; i<n; i++){
            String line = sc.nextLine();
            String[] str = line.split(" ");
            int faVal = Integer.valueOf(str[0]);
            int lchVal = Integer.valueOf(str[1]);
            int rchVal = Integer.valueOf(str[2]);
            
            Node curNode = map.get(faVal);
            if(lchVal != 0){
                curNode.left = new Node(lchVal);
                map.put(lchVal, curNode.left);
            }
            if(rchVal != 0){
                curNode.right = new Node(rchVal);
                map.put(rchVal, curNode.right);
            }
        }
        
        Info info = process(root);
        System.out.println(info.nodesNum);
        
    }
    
    
    public static Info process(Node node){
        Info curInfo = new Info();
        
        if(node == null){
            return curInfo;
        }
        
        Info leftInfo = process(node.left);
        Info rightInfo = process(node.right); 
        curInfo.max = node.right==null ? node.value : rightInfo.max;        
        curInfo.min = node.left==null ? node.value : leftInfo.min;
        
        if(((leftInfo.flag && rightInfo.flag) != true) ||
          (node.left != null && leftInfo.max>node.value) ||
          (node.right != null && rightInfo.min<node.value)){
            curInfo.flag = false;
            curInfo.nodesNum = Math.max(leftInfo.nodesNum, rightInfo.nodesNum);            
            return curInfo;
        }
        
        curInfo.nodesNum = leftInfo.nodesNum + rightInfo.nodesNum + 1;
        
        
        return curInfo;
    }
    
}


编辑于 2022-05-24 22:22:40 回复(0)
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

class TreeNode{
public:
    int val;
    TreeNode* left, * right;
    TreeNode(int val = 0, TreeNode* left = nullptr, TreeNode* right = nullptr): 
        val(val), left(left), right(right){}
};

class Solution{
public:
    static bool checkRoot(TreeNode* root, TreeNode* left, TreeNode* right){
        while(right != nullptr && right->left != nullptr) right = right->left;
        while(left != nullptr && left->right != nullptr) left = left->right;
        if((left == nullptr || left->val < root->val) && 
           (right == nullptr || right->val > root->val)){
               return true;
        }
        return false;
    }
    static pair<int, TreeNode*> getMaxBSTree(TreeNode* root){
        if(root == nullptr) return make_pair(0, nullptr);
        int rootResSize = 0;
        pair<int, TreeNode*> rootRes;
        pair<int, TreeNode*> leftRes = getMaxBSTree(root->left);
        pair<int, TreeNode*> rightRes = getMaxBSTree(root->right);
        if (leftRes.second == root->left && rightRes.second == root->right
          && checkRoot(root, root->left, root->right)){
            rootResSize = leftRes.first + rightRes.first + 1;
            rootRes.first = rootResSize;
            rootRes.second = root;
        }else{            
            rootRes = leftRes.first > rightRes.first ? leftRes : rightRes; 
        }
        return rootRes;
    }
};

int main(){
    int n, rootVal;
    int line[3];
    TreeNode* root = nullptr;
    unordered_map<int, TreeNode*> treeNodes;
    treeNodes.insert(make_pair(0, nullptr));
    cin >> n >> rootVal;
    while(n--){
        cin >> line[0] >> line[1] >> line[2];
        for(int i = 0; i < 3; i++){
            if(treeNodes.count(line[i]) == 0){
                treeNodes.insert(make_pair(line[i], new TreeNode(line[i])));
            }            
        }
        treeNodes[line[0]]->left = treeNodes[line[1]];
        treeNodes[line[0]]->right = treeNodes[line[2]];
    }
    root = treeNodes[rootVal];
    cout << Solution::getMaxBSTree(root).first;
    return 0;
}

发表于 2021-09-21 16:03:20 回复(0)
import java.util.*;

class Node {
    public int val;
    public Node right;
    public Node left;
    public Node (int val) {
        this.val = val;
    }
}

class ReturnType {
    public Node maxBSTHead;
    public int maxBSTSize;
    public int max;
    public int min;
    
    public ReturnType(Node maxBSTHead, int maxBSTSize, int min, int max) {
        this.maxBSTHead = maxBSTHead;
        this.maxBSTSize = maxBSTSize;
        this.min = min;
        this.max = max;
    }
}

public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Node head = constructTree(sc, n);
        int result = returnSize(head);
        System.out.println(result);
    }
    
    public static Node constructTree (Scanner sc, int n) {
        HashMap<Integer, Node> map = new HashMap<>();
        int rootVal = sc.nextInt();
        Node root = new Node(rootVal);
        map.put(rootVal, root);
        for (int i = 0; i < n; i++) {
            int nodeVal = sc.nextInt();
            int leftVal = sc.nextInt();
            int rightVal = sc.nextInt();
            if (map.containsKey(nodeVal)) {
                Node tmpNode = map.get(nodeVal);
                Node leftNode = leftVal == 0 ? null : new Node(leftVal);
                Node rightNode = rightVal == 0 ? null : new Node(rightVal);
                tmpNode.left = leftNode;
                tmpNode.right = rightNode;
                if (leftVal != 0)
                    map.put(leftVal, leftNode);
                if (rightVal != 0)
                    map.put(rightVal, rightNode);
            }
        }
        return root;
    }
    
    public static int returnSize (Node head) {
        return process(head).maxBSTSize;
        
    }
    
    public static ReturnType process (Node x) {
        //base case:最小值是系统最大,最大值是系统最小
        if (x == null)
            return new ReturnType(null, 0, Integer.MAX_VALUE, Integer.MIN_VALUE);
        //默认直接得到左右树全部信息
        ReturnType leftData = process(x.left);
        ReturnType rightData = process(x.right);
        //信息整合:
        /*
        同时对以x为头的子树也做同样要求,也需要返回如ReturnType描述的全部信息
        */
        int min = Math.min(x.val, Math.min(leftData.min, rightData.min));
        int max = Math.max(x.val, Math.max(leftData.max, rightData.max));
        int maxBSTSize = Math.max(leftData.maxBSTSize, rightData.maxBSTSize);
        Node maxBSTHead = leftData.maxBSTSize >= rightData.maxBSTSize ? leftData.maxBSTHead: rightData.maxBSTHead;
        if (leftData.maxBSTHead == x.left && rightData.maxBSTHead == x.right && x.val > leftData.max && x.val < rightData.min) {
            maxBSTSize = leftData.maxBSTSize + rightData.maxBSTSize + 1;
            maxBSTHead = x;
        }
        return new ReturnType(maxBSTHead, maxBSTSize, min, max);
    }
}

发表于 2021-06-13 20:49:34 回复(0)
//参考左神
import java.util.*;
public class Main{
    static class Node{
        int key;
        Node left;
        Node right;
        
        Node(int k){key = k;}
    }
    
    static Map<Integer, Node> map = new HashMap<>();
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        //0->size; 1->min; 2->max
        int[] record = new int[3];
        int n = sc.nextInt(), rootVal = sc.nextInt();
        Node root = new Node(rootVal);
        map.put(rootVal, root);
        while(sc.hasNext()){
            int father = sc.nextInt();
            int leftV = sc.nextInt(), rightV = sc.nextInt();
            Node left = leftV == 0 ? null : new Node(leftV);
            if(left != null) map.put(left.key, left);
            Node right = rightV == 0 ? null : new Node(rightV);
            if(right != null)map.put(right.key, right);
            Node f = map.get(father);
            f.left = left;
            f.right = right;
        }
        posOrder(root, record);
        System.out.print(record[0]);
    }
    
    static Node posOrder(Node head, int[]record){
        if(head == null){
            record[0] = 0;
            record[1] = Integer.MAX_VALUE;
            record[2] = Integer.MIN_VALUE;
            return null;
        }
        int val = head.key;
        Node lBst = posOrder(head.left, record);
        int lSize = record[0], lMin = record[1], lMax = record[2];
        Node rBst = posOrder(head.right, record);
        int rSize = record[0], rMin = record[1], rMax = record[2];
        record[1] = Math.min(lMin, val);
        record[2] = Math.max(rMax, val);
        if(lBst == head.left && rBst == head.right &&  val > lMax && val < rMin){
            record[0] = lSize + rSize + 1;
            return head;
        }
        record[0] = Math.max(lSize, rSize);
        return lSize > rSize ? lBst : rBst;
    }
}

发表于 2020-08-26 11:43:15 回复(0)
#include <bits/stdc++.h>
#define maxn 1000001
using namespace std;

struct Node{
    int val;
    Node* left;
    Node* right;
};

Node nodes[maxn];
struct Data{
    int min;
    int max;
    int size;
    Node* head;
    Data(int mi, int ma, int nod, Node* hea){
        min = mi;
        max = ma;
        size = nod;
        head = hea;
    }
};

Data process(Node* root){
    if(root == NULL){
        return Data(INT_MAX, INT_MIN, 0, root);
    }
    Data leftNode = process(root->left);
    Data rightNode = process(root->right);
    int together = 0;
    if(leftNode.head == root->left 
       && rightNode.head == root->right 
       && leftNode.max < root->val 
       && rightNode.min > root->val
      ) {
        together = leftNode.size + rightNode.size + 1;
    }
    int maxSize = max(max(leftNode.size, rightNode.size), together);
    Node* maxHead = leftNode.size > rightNode.size ? leftNode.head : rightNode.head;
    if(maxSize == together) {
        maxHead = root;
    }
    return Data(min(min(leftNode.min,rightNode.min),root->val),
                max(max(leftNode.max,rightNode.max),root->val),
                maxSize,
                maxHead);
}
int main()
{
    int n,r;
    scanf("%d%d",&n,&r);
    for(int i=0;i<n;i++){
        int index,left,right;
        scanf("%d%d%d",&index,&left,&right);
        nodes[index].val = index;
        if(left)
            nodes[index].left = &nodes[left];
        else
            nodes[index].left = NULL;
        if(right)
            nodes[index].right = &nodes[right];
        else
            nodes[index].right = NULL;
    }
    int res = process(&nodes[r]).size;
    printf("%d\n",res);
    return 0;
}

发表于 2020-02-08 21:00:01 回复(1)