面试算法52：展平二叉搜索树

本文主要是介绍面试算法52：展平二叉搜索树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

给定一棵二叉搜索树，请调整节点的指针使每个节点都没有左子节点。调整之后的树看起来像一个链表，但仍然是二叉搜索树。

分析

看起来需要按照节点的值递增的顺序遍历二叉搜索树中的每个节点，并将节点用指向右子节点的指针连接起来。这就容易让人联想到二叉树的中序遍历，只是在这里每遍历到一个节点要把前一个节点的指向右子节点的指针指向它。

解

public class Test {public static void main(String[] args) {TreeNode node1 = new TreeNode(1);TreeNode node2 = new TreeNode(2);TreeNode node3 = new TreeNode(3);TreeNode node4 = new TreeNode(4);TreeNode node5 = new TreeNode(5);TreeNode node6 = new TreeNode(6);node4.left = node2;node4.right = node5;node2.left = node1;node2.right = node3;node5.right = node6;TreeNode result = increasingBST(node4);System.out.println(result);}public static TreeNode increasingBST(TreeNode root) {Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;TreeNode prev = null;TreeNode first = null;while (cur != null || !stack.isEmpty()) {while (cur != null) {stack.push(cur);cur = cur.left;}cur = stack.pop();if (prev != null) {prev.right = cur;}else {first = cur;}prev = cur;cur.left = null;cur = cur.right;}return first;}
}

附

中序遍历的迭代算法：

public class Test {public static void main(String[] args) {TreeNode node1 = new TreeNode(1);TreeNode node2 = new TreeNode(2);TreeNode node3 = new TreeNode(3);TreeNode node4 = new TreeNode(4);TreeNode node5 = new TreeNode(5);TreeNode node6 = new TreeNode(6);node4.left = node2;node4.right = node5;node2.left = node1;node2.right = node3;node5.right = node6;List<Integer> result = inorderTraversal(node4);System.out.println(result);}public static List<Integer> inorderTraversal(TreeNode root) {List<Integer> nodes = new LinkedList<>();Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while (cur != null || !stack.isEmpty()) {while (cur != null) {stack.push(cur);cur = cur.left;}cur = stack.pop();nodes.add(cur.val);cur = cur.right;}return nodes;}
}

这篇关于面试算法52：展平二叉搜索树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---