Fackbook 下午刚电面的面筋

yanggao1119 发表于 2016-2-19 09:52
个人感觉，楼上解法mix了recursive solution，和iterative solution，不够简明。

我的iterative solutio ...

Hi 你这个里面其实最后prev和tail指向的是同一个node吧，其实就是可以省略tail节点的

tsingpg 发表于 2016-2-21 00:22
Hi 你这个里面其实最后prev和tail指向的是同一个node吧，其实就是可以省略tail节点的

赞！ great suggestion！我改了下，为了语义考虑，用head和tail：

        public TreeNode BT2CircularDLL(TreeNode root) {
                if (root == null) {
                        return root;
                }
                Stack<TreeNode> st = new Stack<>();
                TreeNode curr = root;
                TreeNode head = null;
                TreeNode tail = null;
                while (curr != null || !st.isEmpty()) {
                        if (curr != null) {
                                st.push(curr);
                                curr = curr.left;
                        } else {
                                TreeNode popped = st.pop();
                                if (tail != null) {
                                        tail.right = popped;
                                        popped.left = tail;
                                } else {
                                        head = popped;
                                }
                                tail = popped;
                                curr = popped.right;
                        }
                }
                tail.right = head;
                head.left = tail;
                return head;
        }

答得不错，楼主加油！早日拿到offer