V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Acceml
V2EX  ›  程序员

[Leetcode] 114. 二叉树展开为链表

  •  
  •   Acceml ·
    Acceml · 2019-04-15 23:36:33 +08:00 · 1222 次点击
    这是一个创建于 1808 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目

    给定一个二叉树,原地将它展开为链表。

    例如,给定二叉树

        1
       / \
      2   5
     / \   \
    3   4   6
    

    将其展开为:

    1
     \
      2
       \
        3
         \
          4
           \
            5
             \
              6
    

    题解

    这算是比较经典的一道题目了, 博主面试快手的时候原题。最开始一想,觉得递归的求解不就好了,但是递归的时候发现需要注意一个地方就是:需要先递归右子树,然后记录下右子树展开完成之后的链表头。然后再递归的求解左子树,把左子树的最后一个链到右子树的链表头。基于这个,我们用一个 pre 指针来记录右子树的头结点。 image

    class Solution {
        private TreeNode prev = null;
    
        public void flatten(TreeNode root) {
            if (root == null)
            return;
            flatten(root.right);
            flatten(root.left);
            root.right = prev;
            root.left = null;
            prev = root;
        }
    }
    

    递归的方式转换为迭代的方式用 stack 就好了,反而比较好理解。

    class Solution {
        public void flatten(TreeNode root) {
            if (root == null) return;
            Stack<TreeNode> stack = new Stack<TreeNode>();
            stack.push(root);
            while (!stack.isEmpty()) {
                TreeNode current = stack.pop();
                if (current.right != null) stack.push(current.right);
                if (current.left != null) stack.push(current.left);
                if (!stack.isEmpty()) current.right = stack.peek();
                current.left = null;
            }
        }
    }
    

    Leetcode 名企之路 有问题加手撕代码 QQ 群讨论:805423079

    目前尚无回复
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3278 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 11:51 · PVG 19:51 · LAX 04:51 · JFK 07:51
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.