LeetCode 的 Java 题目，同样的数据，本地能过测试但是在线过不了

2022-06-19 20:15:42 +08:00
 movq

题目：

https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/

就是一个二叉搜索树，两个节点 p 和 q 找到最近公共祖先。这个树最大节点数目是 100000(虽然题目没说，但是我在美国 leetcode 里面找到了说明，而且在美国 leetcode 和这里提交，报错情况一模一样）

我的做法是先把这个树变成一个 index 为 1 对应 root 的数组vals，左子树 index 是 2*index, 右子树是 2*index+1 。

找到 p 的 index 是 pIndex ，q 的 index 是 qIndex ，然后在 boolean 数组visited里面把 p 的 parent 都标记为 true ，然后分析 q ，q 的第一个 visited 为 true 的地方就是最近的公共节点。

代码是这样：

class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null) {
                return null;
            }
            final int maxSize = 9000000;
            int[] vals = new int[maxSize];
            TreeNode[] nodes = new TreeNode[maxSize];
            boolean[] visited = new boolean[maxSize];
            var nodeStack = new ArrayDeque<TreeNode>();
            var indexStack = new ArrayDeque<Integer>();
            nodeStack.offerLast(root);
            indexStack.offerLast(1);
            int pIndex = 0, qIndex = 0;
            while (nodeStack.size() != 0) {
                var node = nodeStack.pollFirst();
                var index = indexStack.pollFirst();
                vals[index] = node.val;
                nodes[index] = node;
                if (node == p) {
                    pIndex = index;
                } else if (node == q) {
                    qIndex = index;
                }
                if (node.left != null) {
                    nodeStack.offerLast(node.left);
                    indexStack.offerLast(2 * index);
                }
                if (node.right != null) {
                    nodeStack.offerLast(node.right);
                    indexStack.offerLast(2 * index + 1);
                }
            }
            while (pIndex >= 1) {
                visited[pIndex] = true;
                pIndex /= 2;
            }
            TreeNode answer = null;
            while (qIndex >= 1) {
                if (visited[qIndex]) {
                    answer = nodes[qIndex];
                    break;
                }
                qIndex /= 2;
            }
            return answer;
        }
    }

报错是:

java.lang.ArrayIndexOutOfBoundsException: Index 12694084 out of bounds for length 9000000
  at line 21, Solution.lowestCommonAncestor
  at line 55, __DriverSolution__.__helper__
  at line 102, __Driver__.main

也就是说，我在第一个 while 里面第三行 val[index] = node.val 时，index 超过了 900000.

但是我在本地测试同样的数据，没有任何问题，能给出正确答案。

从逻辑上说，这个测试数据集给出了 20000 个节点，也不可能让 index 达到报错里面所说的 12694084 。。。(很简单的逻辑。。。）

真不知道出了什么问题。。。

3143 次点击
所在节点    程序员
26 条回复
movq
2022-06-19 20:17:19 +08:00
报错的数据集（因为一次回复太多会提示失败，所以分几层发一下。。）
movq
2022-06-19 20:17:30 +08:00
[41,6,8469,0,22,6336,9177,null,3,15,31,5734,6509,8770,9379,2,4,10,20,28,39,1490,5775,6410,6986,8493,8823,9298,9975,1,null,null,5,8,12,16,21,26,29,34,40,506,4491,5737,6034,6384,6434,6853,8178,8492,8503,8779,9106,9283,9339,9774,9982,null,null,null,null,7,9,11,13,null,17,null,null,23,27,null,30,32,35,null,null,176,837,3317,5715,5735,5743,5944,6310,6338,6398,6425,6436,6802,6917,7473,8397,8472,null,8494,8711,8776,8782,9009,9153,9210,9289,9336,9371,9400,9953,9980,9993,null,null,null,null,null,null,null,14,null,18,null,25,null,null,null,null,null,33,null,36,53,316,739,1409,3011,3924,4845,5730,null,5736,5741,5754,5807,5968,6056,6329,6337,6345,6387,6400,6420,6428,6435,6467,6575,6814,6911,6970,7111,7761,8283,8461,8470,8473,null,8496,8674,8722,8773,8778,8780,8803,8924,9078,9111,9172,9185,9270,9285,9296,9307,9337,9369,9376,9391,9633,9933,9967,9979,9981,9989,9994,null,null,null,19,24,null,null,null,null,37,46,140,199,505,669,814,1281,1430,1976,3096,3627,3934,4646,5455,5719,5733,null,null,5740,5742,5752,5758,5790,5828,5948,5974,6051,6278,6326,6331,null,null,6339,6365,6385,6388,6399,6405,6417,6424,6426,6433,null,null,6441,6492,6572,6739,6808,6845,6867,6915,6931,6985,7086,7463,7758,7797,8179,8349,8421,8467,null,8471,null,8476,8495,8497,8576,8708,8719,8761,8771,8774,8777,null,null,8781,8793,8806,8882,8937,9054,9084,9107,9134,9166,9175,9181,9187,9255,9282,9284,9287,9292,9297,9305,9319,null,9338,9342,9370,9375,9378,9380,9396,9546,9713,9798,9946,9956,9973,9978,null,null,null,9986,9991,null,9999,null,null,null,null,null,38,45,49,111,175,196,203,352,null,631,673,799,832,1056,1366,1415,1480,1819,2471,3016,3223,3532,3770,3931,4018,4592,4835,5233,5477,5718,5728,5732,null,5739,null,null,null,5745,5753,5756,5766,5785,5803,5823,5875,5946,5950,5971,5994,6043,6052,6124,6298,6317,6328,6330,6332,null,6341,6348,6369,null,6386,null,6396,null,null,6404,6408,6415,6419,6422,null,null,6427,6430,null,6440,6458,6471,6503,6520,6574,6721,6750,6807,6810,6843,6849,6863,6893,6912,6916,6919,6947,6983,null,6993,7088,7124,7466,7703,7759,7787,7962,null,8195,8331,8362,8411,8453,8462,8468,null,null,8474,8482,null,null,null,8500,8573,8619,8682,8710,8712,8721,8755,8767,null,8772,null,8775,null,null,null,null,8787,8795,8805,8819,8862,8886,8929,8978,9014,9076,9080,9087,null,9110,9112,9139,9163,9170,9173,9176,9178,9183,9186,9188,9240,9267,9278,null,null,null,9286,9288,9290,9293,null,null,9303,9306,9312,9326,null,null,9340,9366,null,null,9374,null,9377,null,null,9383,9393,9397,9493,9601,9652,9726,9789,9905,9942,9947,9954,9959,9969,9974,9976,null,9984,9988,9990,9992,9997,null,null,null,44,null,48,52,92,125,156,null,183,197,202,235,325,366,629,656,670,712,746,802,816,835,1026,1212,1293,1403,1414,1420,1471,1483,1604,1903,2432,2870,3014,3062,3219,3311,3336,3565,3730,3918,3927,3933,3975,4330,4546,4627,4709,4840,5158,5399,5456,5697,5716,null,5727,5729,5731,null,5738,null,5744,5746,
movq
2022-06-19 20:18:25 +08:00
null,null,5755,5757,5762,5774,5778,5786,5795,5805,5822,5824,5848,5895,5945,5947,5949,5961,5969,5973,5976,6014,6042,6049,null,6053,6117,6139,6290,6308,6314,6320,6327,null,null,null,null,6335,6340,6344,6346,6354,6366,6383,null,null,6390,6397,6401,null,6406,6409,6413,6416,6418,null,6421,6423,null,null,6429,6431,6438,null,6443,6462,6470,6472,6497,6506,6512,6528,6573,null,6648,6733,6748,6767,6805,null,6809,6813,6828,6844,6847,6852,6854,6864,6875,6910,null,6914,null,null,6918,6922,6944,6968,6976,6984,6991,7047,7087,7091,7112,7260,7464,7467,7656,7740,null,7760,7774,7795,7876,8110,8187,8202,8315,8341,8359,8391,8410,8414,8448,8455,null,8463,null,null,null,8475,8478,8483,8498,8502,8531,8575,8600,8624,8681,8688,8709,null,null,8716,8720,null,8735,8760,8766,8768,null,null,null,null,8784,8791,8794,8797,8804,null,8815,8820,8825,8867,8884,8887,8927,8936,8974,8986,9013,9041,9067,9077,9079,9081,9086,9093,9109,null,null,9119,9138,9144,9159,9164,9167,9171,null,9174,null,null,null,9179,9182,9184,null,null,null,9189,9223,9247,9258,9269,9275,9279,null,null,null,null,null,9291,null,9295,9301,9304,null,null,9310,9315,9324,9330,null,9341,9358,9367,9372,null,null,null,9382,9386,9392,9395,null,9398,9488,9509,9547,9616,9643,9702,9721,9761,9780,9795,9821,9927,9936,9944,null,9951,null,9955,9958,9965,9968,9972,null,null,null,9977,9983,9985,9987,null,null,null,null,null,9995,9998,42,null,47,null,50,null,66,106,117,138,142,172,182,191,null,198,200,null,216,285,317,330,355,483,553,630,649,667,null,671,704,725,744,778,801,807,815,825,834,836,909,1031,1139,1264,1289,1338,1385,1406,1413,null,1419,1428,1465,1478,1481,1488,1509,1651,1823,1905,2376,2436,2855,2969,3013,3015,3058,3071,3167,3220,3266,3314,3328,3407,3562,3595,3629,3740,3910,3921,3925,3929,3932,null,3965,4010,4107,4346,4499,4588,4626,4630,4665,4741,4839,4843,5052,5215,5275,5454,null,5464,5500,5705,null,5717,5725,null,null,null,null,null,null,null,null,null,null,5749,null,null,null,null,5761,5764,5770,null,5777,5783,null,5788,5791,5802,5804,5806,5818,null,null,5826,5831,5851,5876,5909,null,null,null,null,null,null,5951,5965,null,5970,5972,null,5975,5991,5996,6021,6038,null,6048,6050,null,6055,6081,6120,6130,6176,6282,6295,6306,6309,6312,6316,6319,6322,null,null,6334,null,null,null,6343,null,null,6347,6351,6363,null,6368,6382,null,6389,6391,null,null,null,6403,null,6407,null,null,6411,6414,null,null,null,null,null,null,null,null,null,null,null,6432,6437,6439,6442,6456,6461,6463,6469,null,null,6484,6496,6499,6504,6507,6511,6519,6526,6547,null,null,6615,6702,6726,6734,6741,6749,6763,6768,6804,6806,null,null,6812,null,6823,6835,null,null,6846,6848,6851,null,null,6857,null,6866,6872,6876,6894,null,6913,null,null,null,6921,6929,6940,6946,6950,6969,6971,6978,null,null,6989,6992,7011,7083,null,null,7089,7101,null,7117,7125,7323,null,7465,null,7470,7487,7672,7730,7749,null,null,7773,7776,7792,7796,7817,7958,8093,8124,8186,8191,8200,8276,8300,8318,8339,8346,8350,8360,8388,8392,8399,null,8412,8416,8425,8452,8454,8460,null,8464,null,null,8477,8479,null,8491,null,8499,8501,null,8524,8543,8574,null,8586,8609,8623,8637,8675,null,8685,8695,null,null,8715,8718,null,null,8733,8743,8758,null,8763,null,null,8769,8783,8785,8788,8792,null,null,8796,8798,null,null,8810,8817,null,8822,8824,8826,8866,8878,8883,8885,null,8918,8925,8928,8934,null,8946,8976,8984,9004,9012,null,9021,9048,9064,9074,null,null,null,null,null,9082,9085,null,9089,9103,9108,null,9118,9133,9137,null,9142,9147,9154,9162,null,9165,null,9168,null,null,null,null,null,9180,null,null,null,null,null,9199,9215,9233,9242,9249,9256,9261,9268,null,9272,9276,null,9281,null,null,9294,null,9299,9302,null,null,9308,9311,9313,9316,9322,9325,9329,9334,null,null,9343,9363,null,9368,null,9373,9381,null,9384,9388,null,null,9394,null,null,9399,9480,9489,9505,9513,null,9571,9607,9618,9639,9649,9698,9705,9718,9725,9747,9764,9778,9782,9791,9797,9812,9853,9914,9932,9934,9941,9943,9945,9949,9952,null,null,9957,null,9962,9966,null,null,9970,null,null,null,null,null,null,null,null,null,null,9996,null,null,null,43,null,null,null,51,56,82,101,108,114,120,132,139,141,153,164,173,179,null,185,192,null,null,null,201,211,229,270,315,null,319,328,337,354,357,420,485,517,557,null,null,646,651,658,668,null,672,699,709,721,736,741,745,755,786,800,null,803,811,null,null,820,830,833,null,null,null,854,925,1028,1035,1136,1180,1262,1279,1284,1292,1324,1339,1382,1397,1405,1407,1412,null,1417,null,1421,1429,1438,1469,1474,1479,null,1482,1484,1489,1497,1519,1615,1814,1821,1837,1904,1957,2010,2413,2434,2451,2785,2857,2885,3002,3012,null,null,null,3053,3059,3067,3074,3119,3213,null,3221,3248,3308,3312,3316,3325,3334,3370,3422,3552,3564,3585,3623,3628,3715,3738,3741,3827,3914,3920,3922,null,3926,3928,3930,null,null,3939,3970,3997,4015,4033,4189,4333,4465,4498,4510,4547,4589,4623,null,4629,4636,4653,4702,4722,4770,4836,null,4842,4844,4902,5131,5208,5224,5258,5349,5417,null,5459,5470,5478,5631,5700,5711,null,null,5724,5726,5747,5750,5760,null,5763,5765,5769,5772,5776,null,5780,5784,5787,5789,null,5792,5801,null,null,null,null,null,5810,5821,5825,5827,5830,5836,5849,5870,null,5884,5904,5916,null,5959,5964,5967,null,null,null,null,null,null,5985,5992,5995,6007,6017,6024,6037,6039,
movq
2022-06-19 20:18:43 +08:00
6047,null,null,null,6054,null,6077,6085,6118,6123,6126,6137,6158,6230,6279,6285,6291,6297,6299,6307,null,null,6311,6313,6315,null,6318,null,6321,6324,6333,null,6342,null,null,null,6350,6353,6356,6364,6367,null,6377,null,null,null,null,6394,6402,null,null,null,null,6412,null,null,null,null,null,null,null,null,null,null,6455,6457,6460,null,null,6464,6468,null,6480,6490,6494,null,6498,6501,null,6505,null,6508,6510,null,6513,null,6525,6527,6532,6570,6585,6622,6676,6704,6725,6730,null,6736,6740,6746,null,null,6756,6766,null,6793,6803,null,null,null,6811,null,6817,6827,6831,6840,null,null,null,null,6850,null,6855,6862,6865,null,6871,6874,null,6889,null,6903,null,null,6920,null,6923,6930,6938,6943,6945,null,6948,6957,null,null,null,6975,6977,6979,6987,6990,null,null,6995,7037,7074,7085,null,7090,7094,7109,7116,7123,null,7205,7264,7390,null,null,7469,7471,7483,7540,7667,7675,7706,7736,7745,7751,7766,null,7775,7780,7789,7794,null,null,7802,7857,7883,7960,8079,8101,8115,8142,8184,null,8188,8194,8197,8201,8253,8280,8289,8307,8317,8325,8337,8340,8343,8347,null,8351,null,8361,8366,8389,null,8396,8398,8405,null,8413,8415,8419,8423,8431,8450,null,null,null,8458,null,null,8466,null,null,null,8481,8484,null,null,null,null,null,8504,8527,8542,8551,null,null,8578,8590,8605,8612,8621,null,8636,8638,null,8677,8684,8687,8692,8701,8714,null,8717,null,8726,8734,8736,8751,8757,8759,8762,8765,null,null,null,null,null,8786,null,8790,null,null,null,null,null,8800,8809,8814,8816,8818,8821,null,null,null,null,8849,8864,null,8873,8881,null,null,null,null,8889,8920,null,8926,null,null,8933,8935,8938,8973,8975,8977,8983,8985,8997,9007,9011,null,9015,9035,9045,9049,9056,9065,9068,9075,null,9083,null,null,9088,9090,9102,9104,null,null,9113,null,9122,null,9136,null,9141,9143,9146,9149,null,9158,9160,null,null,null,null,9169,null,null,9195,9208,9212,9217,9232,9237,9241,9246,9248,9250,null,9257,9260,9265,null,null,9271,9274,null,9277,9280,null,null,null,null,9300,null,null,null,9309,null,null,null,9314,null,9317,9321,9323,null,null,9328,null,9331,9335,null,9353,9361,9364,null,null,null,null,null,null,null,9385,9387,9390,null,null,null,null,9428,9484,null,9490,9501,9506,9511,9538,9559,9600,9603,9608,9617,9629,9636,9641,9647,9650,9678,9701,9704,9710,9715,9719,9723,null,9743,9755,9762,9769,9777,9779,9781,9788,9790,9792,9796,null,9799,9820,9834,9877,9907,9916,9930,null,null,9935,9939,null,null,null,null,null,9948,9950,null,null,null,null,9961,9964,null,null,null,9971,null,null,null,null,null,null,54,60,68,91,95,102,107,110,112,115,119,124,131,135,null,null,null,null,152,155,160,167,null,174,178,181,184,190,null,195,null,null,205,213,223,230,239,273,294,null,318,322,326,329,334,350,353,null,356,360,368,459,484,504,507,524,556,611,632,647,650,654,657,663,null,null,null,null,678,700,706,711,717,723,730,738,740,742,null,null,750,766,782,789,null,null,null,804,810,813,817,824,829,831,null,null,845,863,918,994,1027,1030,1033,1037,1090,1137,1159,1192,1256,1263,1275,1280,1283,1286,1291,null,1309,1327,null,1342,1376,1384,1394,1402,1404,null,null,1408,1410,null,1416,1418,null,1422,null,null,1431,1446,1468,1470,1472,1475,null,null,null,null,null,1486,null,null,1493,1498,1513,1520,1613,1640,1808,1815,1820,1822,1836,1897,null,null,1930,1975,2009,2179,2384,2431,2433,2435,2449,2452,2713,2803,2856,2865,2876,2941,2971,3003,null,null,3038,3056,null,3060,3064,3068,3072,3078,3111,3143,3197,3215,null,3222,3227,3261,3295,3309,null,3313,3315,null,3322,3327,3333,3335,3357,3389,3411,3461,3541,3554,3563,null,3583,3591,3604,3625,null,null,3709,3721,3732,3739,null,3760,3822,3874,3913,3916,3919,null,null,3923,null,null,null,null,null,null,3935,3955,3968,3973,3988,4004,4012,4016,4020,4066,4159,4234,4331,4334,4370,4467,4496,null,4504,4521,null,4552,null,4591,4594,4625,4628,null,4633,4641,4651,4661,4693,4707,4715,4739,4749,4781,null,4838,4841,null,null,null,4857,4933,5117,5142,5194,5212,5220,5231,5250,5271,5288,5378,5400,5444,5458,5463,5466,5471,null,5486,5548,5643,5698,5701,5709,5712,5721,null,null,null,null,5748,null,5751,5759,null,null,null,null,null,5768,null,5771,5773,null,null,5779,5781,null,null,null,null,null,null,null,5793,5798,null,5809,5816,5819,null,null,null,null,null,5829,null,5832,5837,null,5850,5852,5871,5879,5889,5899,5908,5911,5939,5953,5960,5962,null,5966,null,5980,5989,null,5993,null,null,6001,6009,6015,6019,6022,6029,6035,null,null,6041,6045,null,null,null,6066,6080,6084,6114,null,6119,6121,null,6125,6127,6132,6138,6153,6166,6185,6276,null,6281,6284,6289,null,6293,6296,null,null,6304,null,null,null,null,null,null,null,null,null,null,null,null,6323,6325,null,null,null,null,6349,null,6352,null,6355,6357,null,null,null,null,6370,6378,6393,6395,null,null,null,null,6447,null,null,null,6459,null,null,6466,null,null,6476,6482,6488,6491,6493,6495,null,null,6500,6502,null,null,null,null,null,null,null,6518,6521,null,null,null,6531,6541,6567,6571,6578,6589,6618,6635,6657,6683,6703,6720,6723,null,6729,6732,6735,6738,null,null,6744,6747,6755,6757,6764,null,6774,6801,null,null,null,null,6816,6822,6824,null,6830,6832,6836,6842,null,null,null,6856,6858,null,null,null,6870,null,6873,null,6885,6892,6896,6904,null,null,null,6926,null,null,6932,6939,6941,null,null,null,null,6949,6954,6964,6972,null,null,null,null,6982,null,6988,null,null,6994,7001,7016,7040,7050,7079,7084,null,null,null,7093,7095,7108,7110,7115,null,7119,null,7130,7238,7263,7280,7376,7394,7468,null,null,7472,7481,7485,7503,7635,7660,7670,7673,7684,7705,7729,7731,7737,7741,7748,7750,7754,7762,7772,null,null,7779,7782,7788,7791,7793,null,7801,7807,7843,7862,7879,7916,7959,7961,7989,8088,8100,8108,8112,8120,8135,8152,8183,8185,null,8190,8192,null,8196,8199,null,null,8234,8256,8277,8281,8287,8294,8301,8312,8316,null,8322,8328,8332,8338,null,null,8342,8344,null,8348,null,8353,null,null,8365,8375,null,8390,8395,null,null,null,8401,8406,null,null,null,null,8418,8420,8422,8424,8430,8433,8449,8451,8457,8459,8465,null,8480,null,null,8485,null,8513,8526,8529,8534,null,8547,8571,8577,8581,8587,8597,8604,8606,8611,8618,8620,8622,8633,null,null,8665,8676,8680,8683,null,8686,null,8691,8693,8700,8704,8713,null,null,null,8725,8727,null,null,null,8742,8750,8754,8756,null,null,null,null,null,8764,null,null,null,8789,null,8799,8801,8808,null,8812,null,null,null,null,null,null,null,8845,8857,8863,8865,8868,8875,8880,null,8888,8909,8919,8922,null,null,8930,null,null,null,null,8942,8949,null,null,null,null,null,8982,null,null,null,8996,8998,9006,9008,9010,null,null,9018,9034,9036,9044,9046,null,9052,9055,9058,null,
movq
2022-06-19 20:19:04 +08:00
9066,null,9073,null,null,null,null,null,null,null,9091,9096,null,null,9105,null,9117,9120,9123,9135,null,9140,null,null,null,9145,null,9148,9151,9156,null,null,9161,null,null,9191,9197,9200,9209,9211,9214,9216,9222,9229,null,9236,9238,null,null,9243,null,null,null,null,9254,null,null,9259,null,9263,9266,null,null,9273,null,null,null,null,null,null,null,null,null,null,null,null,9318,9320,null,null,null,9327,null,null,9332,null,null,9346,9354,9360,9362,null,9365,null,null,null,null,9389,null,9410,9438,9482,9486,null,9492,9494,9503,null,9507,9510,9512,9522,9542,9550,9562,9572,null,9602,9605,null,9615,null,null,9621,9632,9634,9637,9640,9642,9645,9648,null,9651,9667,9685,9700,null,9703,null,9708,9712,9714,9716,null,9720,9722,9724,9739,9745,9751,9758,null,9763,9766,9770,9775,null,null,null,null,null,9786,null,null,null,null,9793,null,null,null,9811,9815,null,9832,9852,9858,9898,9906,9909,9915,9920,9928,9931,null,null,9938,9940,null,null,null,null,9960,null,9963,null,null,null,null,55,59,63,67,78,87,null,94,96,null,105,null,null,109,null,null,113,null,116,118,null,121,null,130,null,133,136,146,null,154,null,158,162,166,171,null,null,177,null,180,null,null,null,189,null,193,null,204,209,212,215,221,224,null,234,237,260,271,284,289,305,null,null,321,323,null,327,null,null,332,336,346,351,null,null,null,null,359,364,367,393,453,474,null,null,488,null,null,511,523,526,555,null,569,617,null,634,null,648,null,null,652,655,null,null,660,664,676,682,null,702,705,707,710,null,715,720,722,724,729,732,737,null,null,null,null,743,749,754,756,770,781,784,788,795,null,806,809,null,812,null,null,819,821,null,828,null,null,null,841,847,856,876,913,920,970,1003,null,null,1029,null,1032,1034,1036,1053,1082,1131,null,1138,1142,1165,1191,1199,1246,1257,null,null,1268,1276,null,null,1282,null,1285,1288,1290,null,1303,1312,1325,1330,1341,1359,1372,1377,1383,null,1389,1396,1400,null,null,null,null,null,null,1411,null,null,null,null,null,1426,null,1432,1444,1462,1467,null,null,null,null,1473,null,1476,1485,1487,
movq
2022-06-19 20:22:11 +08:00
好吧这个其实如果有 v 友感兴趣的话可以把我代码复制提交看一下报错信息，从那里面复制比较方便。。。这里发得拆成太多了，不方便看
GuuJiang
2022-06-19 20:25:00 +08:00
你这样相当于用完全二叉树来表示，其中大量不存在的空节点仍然要占用 index ，最简单的一个例子，假如 20000 个节点退化成了链表，也就是说树的高度达到 20000 ，想想这时候 index 需要达到多少
movq
2022-06-19 20:27:00 +08:00
@GuuJiang 你说的是对的，但是问题是这样的：我报错的那个测试用例，里面包括所有的空节点，加起来一共是 20000 个节点。而且本地没出问题
movq
2022-06-19 20:29:53 +08:00
@GuuJiang leetcode 网站上面是这么显示的：

执行结果：
执行出错
显示详情
xxxxxxxxxxx

最后执行的输入：
yyyyyyyyy

我把 yyyyyyyyy （有 20000 个节点）复制到本地测试，发现没问题


那个最后执行的输入，意思到底是说，这个输入没有得到正确结果，

还是说，这个“最后执行的输入”指的是，最后一个得到正确结果的输入？？？

一般不都是显示出错的例子吗
GuuJiang
2022-06-19 20:30:24 +08:00
我说的空节点不仅是显式的空节点，还包括下面所有层，你这样的表示法所需的空间是高度等于原树高度的一棵完全二叉树，画个图就明白问题在哪了
GuuJiang
2022-06-19 20:32:56 +08:00
不要纠结具体的一个测试用例了，你这个思路注定是不可行的，空间复杂度随随便便就爆表了，别说是 20000 个节点了，很容易就能构造出一个表面上看只有几十个结点，但是所需空间超出宇宙中原子个数的树
o02VFqu3gZnZfX8n
2022-06-19 20:33:36 +08:00
原题给的限制是 The number of nodes in the tree is in the range [2, 10^5]
没有说这个二叉树是平衡的，举个极端的例子，整个二叉树是个单链表，用数组来存要不越界要不 Memory Limit Exceeded
movq
2022-06-19 20:34:33 +08:00
@GuuJiang 我说的 20000 个节点，意思就是完全二叉树减去这个完全二叉树最后一层右边一段缺失的节点。

为什么这么说呢？因为 leetcode 给出的二叉树的测试用例，本身是一个数组，这个数组是一个树，扩展成完全二叉树，然后不存在的节点为 null ，写到一个数组里面。

不然它怎么给测试的树呢？
movq
2022-06-19 20:35:29 +08:00
@DaVinci42 你说的是对的，但是为什么报错的那个例子，最多有 20000 个节点，但是也报错了呢
GuuJiang
2022-06-19 20:37:47 +08:00
@movq 你完全理解错 leetcode 对树的表示法了，它的用例里只会包含叶子结点的 null 节点，而不包含“当表示为完全二叉树时下面的层需要补全的那些虚拟 null 节点”数据输入框本身就自带树可视化功能，点开看一眼图就明白问题在哪了
o02VFqu3gZnZfX8n
2022-06-19 20:38:38 +08:00
@movq
假设总共 10 个节点，你用链表试试最后的节点索引是多少，分析下这里复杂度你就明白了
movq
2022-06-19 20:42:52 +08:00
@GuuJiang 确实。。。我发现问题了。。。。
@DaVinci42 我知道你说的复杂度问题是什么意思，我这里出的问题是我对 leetcode 测试用例给出的树的数组表示存在错误的理解。不过还是感谢你的回答。
GuuJiang
2022-06-19 20:48:30 +08:00
你这是刚入门 leetcode 吧？ leetcode 所有涉及到二叉树的题目的表示法都是一样的，你本地没问题说明你本地从 input 数组构造树的过程也是错误的，构造出的树的高度远远小于实际的高度
movq
2022-06-19 20:52:02 +08:00
@GuuJiang 我是按照完全二叉树的方式读入的。。。不过我树的题目没刷多少，大部分入门题我是本地都没测试，过了样例交了就 AC 了，所以没发现自己的读入方式有问题。。。
tidos
2022-06-19 21:00:34 +08:00
我已经放弃 java 改用 js 刷题了，除了双堆感觉方便多了

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://tanronggui.xyz/t/860705

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX