1. 首页
  2. 剑指offer经典面试题

[剑指 Offer 第 2 版第 36 题] “二叉搜索树与双向链表”做题记录

[剑指 Offer 第 2 版第 36 题] “二叉搜索树与双向链表”做题记录

第 36 题:二叉搜索树与双向链表(典型递归问题)

传送门:二叉搜索树与双向链表牛客网 online judge 地址

输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。

要求不能创建任何新的结点,只能调整树中结点指针的指向。

注意

  • 需要返回双向链表最左侧的节点。

例如,输入下图中左边的二叉搜索树,则输出右边的排序双向链表。

liwei2019101112_1.png

思路:

liwei201910115_2.png

分析:参考解答有一定价值,要好好研究一下。画图就清楚解法了。

Python 代码:

  class TreeNode(object):
        def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None


    class Solution(object):

        def convert(self, root):
            """
            :type root: TreeNode
            :rtype: TreeNode
            """
            if root is None:
                return None
            head, _ = self.__dfs(root)

            return head

        def __dfs(self, root):
            """
            返回双向链表的两端
            """
            # 如果这个结点是叶子结点
            if root.left is None and root.right is None:
                return (root, root)

            # 如果有左孩子,还有右边孩子
            if root.left and root.right:
                ll, lr = self.__dfs(root.left)
                rl, rr = self.__dfs(root.right)
                # 下面穿针引线
                lr.right = root
                root.left = lr
                root.right = rl
                rl.left = root
                return (ll, rr)

            # 走到这里,就是二者之一为空
            if root.left:
                ll, lr = self.__dfs(root.left)
                lr.right = root
                root.left = lr
                return (ll, root)

            if root.right:
                rl, rr = self.__dfs(root.right)
                root.right = rl
                rl.left = root
                return (root, rr)

C++ 代码:返回一个 pair

liwei201910110_3.png

Java 代码:

  class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public class Solution {

        private TreeNode linkedListTail;
        private TreeNode res;

        public TreeNode Convert(TreeNode pRootOfTree) {
            convert(pRootOfTree);
            return res;
        }

        /**
         * 中序遍历
         *
         * @param root
         */
        private void convert(TreeNode root) {
            if (root == null) {
                return;
            }
            convert(root.left);
            // 中序遍历真正做事情的地方
            if (linkedListTail == null) { // 对应刚开始的时候
                linkedListTail = root;
                // 在最左边的地方记录需要返回的双向链表的根结点
                res = root;
            } else {
                linkedListTail.right = root;
                root.left = linkedListTail;
                linkedListTail = root;
            }
            convert(root.right);
        }
    }

Python 代码:

  class TreeNode(object):
        def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None


    class Solution(object):

        def __init__(self):
            self.linked_list_tail = None
            self.res = None

        def convert(self, root):
            """
            :type root: TreeNode
            :rtype: TreeNode
            """
            self.__dfs(root)
            return self.res

        # 中序遍历
        def __dfs(self, root):
            if root is None:
                return
            self.__dfs(root.left)

            if self.linked_list_tail is None:
                self.linked_list_tail = root
                self.res = root
            else:
                self.linked_list_tail.right = root
                root.left = self.linked_list_tail
                self.linked_list_tail = root
            self.__dfs(root.right)

Java 代码:分治算法

  public class Solution2 {
        public TreeNode convert(TreeNode root) {
            if (root == null) {
                return root;
            }
            TreeNode left = rightMost(root.left);
            TreeNode right = leftMost(root.right);
            convert(root.left);
            convert(root.right);
            if (left != null) {
                left.right = root;
            }
            root.left = left;
            if (right != null) {
                right.left = root;
            }
            root.right = right;

            // 最后返回最左边的结点
            while (root.left != null) {
                root = root.left;
            }
            return root;
        }

        TreeNode leftMost(TreeNode root) {
            if (root == null) {
                return null;
            }
            while (root.left != null) {
                root = root.left;
            }
            return root;
        }

        TreeNode rightMost(TreeNode root) {
            if (root == null) {
                return null;
            }
            while (root.right != null) {
                root = root.right;
            }
            return root;
        }
    }

C++ 代码:

  class Solution {
    public:
        TreeNode* convert(TreeNode* root) {
            if (!root) return root;
            stack<TreeNode*> st;
            while (root){
                st.push(root);
                root = root->left;
            }
            TreeNode* ans = st.top();
            TreeNode* last = NULL;
            while (!st.empty()){
                TreeNode* tmp = st.top();
                st.pop();
                if (!last) last = tmp;
                else {
                    last->right = tmp;
                    tmp->left = last;
                    last = tmp;
                }
                tmp = tmp->right;
                while (tmp){
                    st.push(tmp);
                    tmp = tmp->left;
                }
            }
            return ans;
        }
    };

Java 代码:

  /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public TreeNode convert(TreeNode root) {
            if (root == null) return null;
            TreeNode dummy = new TreeNode(-1);
            TreeNode pre = dummy;
            Stack<TreeNode> stack = new Stack<>();
            while (root != null || stack.size() != 0){
                while (root != null){
                    stack.push(root);
                    root = root.left;
                }
                if (stack.size() != 0){
                    TreeNode node = stack.pop();
                    pre.right = node;
                    node.left = pre;
                    pre = pre.right;
                    root = node.right;
                }
            }
            dummy.right.left = null;
            dummy = dummy.right;
            return dummy;
        }
    }

Java 代码:

  class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public class Solution {

        private TreeNode linkedListTail;
        private TreeNode res;

        public TreeNode Convert(TreeNode pRootOfTree) {
            convert(pRootOfTree);
            return res;
        }

        /**
         * 中序遍历
         *
         * @param root
         */
        private void convert(TreeNode root) {
            if (root == null) {
                return;
            }
            convert(root.left);
            // 中序遍历真正做事情的地方
            if (linkedListTail == null) {
                linkedListTail = root;
                // 在最左边的地方记录需要返回的双向链表的根结点
                res = root;
            } else {
                linkedListTail.right = root;
                root.left = linkedListTail;
                linkedListTail = root;
            }
            convert(root.right);
        }
    }

参考资料:https://www.nowcoder.com/questionTerminal/947f6eb80d944a84850b0538bf0ec3a5

作者:liweiwei1419

来源:https://liweiwei1419.github.io/sword-for-offer/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

标题:[剑指 Offer 第 2 版第 36 题] “二叉搜索树与双向链表”做题记录

链接:https://www.javajike.com/article/3283.html

« [剑指 Offer 第 2 版第 35 题] “复杂链表的复制”做题记录
[剑指 Offer 第 2 版第 37 题] “序列化二叉树”做题记录»

相关推荐

QR code