面试算法52：展平二叉搜索树-Toy模板网

这篇具有很好参考价值的文章主要介绍了面试算法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;
    }
}

附

中序遍历的迭代算法：文章来源地址https://www.toymoban.com/news/detail-743787.html

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;
    }
}