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

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

  •  
  •   Acceml · 5 天前 · 302 次点击

    题目

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

    例如,给定二叉树

        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

    目前尚无回复
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2114 人在线   最高记录 4385   ·  
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 16ms · UTC 06:44 · PVG 14:44 · LAX 23:44 · JFK 02:44
    ♥ Do have faith in what you're doing.
    沪ICP备16043287号-1