二叉搜索树的第k个节点|博客系列

/*
* 二叉树结点类
*/
class Node {
    constructor(value = 0, left = null, right = null) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
}
/**
* 二叉搜索树的第k个节点
* @param {Node} root
* @param {Number} target
 */
function KthNode(root, target) {
    const arr = []
    inOrderRec(root, arr)
    if (target > 0 && target <= arr.length) {
        return arr[target - 1]
    }
    return null;
}
/*
* 二叉树中序递归遍历
*/
function inOrderRec (node, arr) {
    if (node) {
        inOrderRec(node.left, arr)
        arr.push(node)
        inOrderRec(node.right, arr)
    }
}
/*
* 二叉树中序非递归遍历
*/
// function inOrderUnRec (node) {
//   let list = [];
//   let stack = [];
//   while (stack.length !== 0 || node) {
//     if (node) {
//       stack.push(node);
//       node = node.left;
//     } else {
//       node = stack.pop();
//       list.push(node);
//       node = node.right;
//     }
//   }
//   return list;
// }

const root = new Node(
  2,
  new Node(1),
  new Node(
    5,
    new Node(4),
    new Node(6)
  )
);
console.log(KthNode(root, 3))
// { value: 4, left: null, right: null }