/** * @param {TreeNode} root * @return {TreeNode} */var increasingBST = function (root) { let dummy = new TreeNode() // 创建一个虚拟节点，dummy.right指向新树的根节点 let leaf = dummy // 创建leaf节点，其指向新树的叶子节点，初始值为dummy let stack = [] // 使用栈辅助遍历 let current = root // 使用节点进行遍历
// 中序遍历二叉树 // 遍历的过程中，可能出现current为空，而stack中有元素，即为遍历到树的最底端。 // 也可能出现current有值而stack为空的情况，如遍历到二叉树的根节点。 while (stack.length || current) { // 不断向左下遍历节点，同时将所有节点入栈 // 这样就保证了总是从最左端开始遍历节点 while (current) { stack.push(current) current = current.left }
// 从栈中弹出节点，即为当前遍历的节点 // 弹出节点的顺序为从左到右。 const node = stack.pop()
// 处理中序遍历读取到的节点 // 将当前节点都连接到叶子节点的右子节点 leaf.right = node // 将leaf向右子节点移动，用于连接下一个节点 leaf = leaf.right // 将left设置为null，打断节点原有的连接，避免新树出现环 leaf.left = null
// 不断向右侧遍历树，如果右侧节点为空，则会从栈中弹出当前子树的根节点 // 这样就形成了从左到右的遍历顺序 current = node.right }
// dummy.right指向的是新树的根节点 return dummy.right}
评论