給定一棵二叉搜索樹，請找出其中的第k小的結點，例如， （5，3，7，2，4，6，8） 中，按結點數值大小順序第三小結點的值為4，
分析：二叉搜索樹就是每個節點X，大于其左子樹的值，小于其右子樹的值，其中序排序是遞增的，使用中序遍歷，每遍歷一個節點，k-1,直到k減到1，即為第K小的節點
/* function TreeNode(x) { this.val = x; this.left = null; this.right = null; } */ function KthNode(pRoot, k) { if (pRoot === null || k === 0) { return null; } // 為了能追蹤k，應該把KthNodeCore函式定義在這里面，k應該在KthNodeCore函式外面 function KthNodeCore(pRoot) { let target = null; if (pRoot.left !== null) { target = KthNodeCore(pRoot.left, k); } if (target === null) { if (k === 1) { target = pRoot; } k--; } if (target === null && pRoot.right !== null) { target = KthNodeCore(pRoot.right, k); } return target; } return KthNodeCore(pRoot); }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/131635.html
標籤：JavaScript
上一篇：vue分類頁開發--axios資料獲取，localstorage資料快取
下一篇：資料流中的中位數