LeetCode二叉树算法——114. 二叉树展开为链表（原地算法）

迷南。 2021-10-15 05:45 211阅读 0赞

题目描述：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoaWppdWppdTMz_size_16_color_FFFFFF_t_70]  
这里主要记录一下什么是原地算法：

开始我以为原地算法必需是指空间复杂度为1

但实际上

原地算法：是直接在原来的节点上改变指向，返回值为void，空间复杂度并没有要求

这题解法很多，我看到题目马上就想到就是比较暴力的解法：

非递归先序遍历二叉树，将结点存在集合中，在遍历集合，令其左子树为空，右子树为下一个元素

代码如下：

/** * 原地算法：是直接在原来的节点上改变指向，返回值为void，空间复杂度并没有要求， */
        public void flatten(TreeNode root) { 
            if (root == null) { 
                return;
            }
            Stack<TreeNode> nodes = new Stack<>();
            List<TreeNode> list = new ArrayList<>();
            nodes.add(root);
            while (!nodes.empty()) { 
                TreeNode pop = nodes.pop();
                list.add(pop);
                if (pop.right != null) { 
                    nodes.push(pop.right);
                }
                if (pop.left != null) { 
                    nodes.push(pop.left);
                }
            }
            for (int i = 0, size = list.size(); i < size; i++) { 
                if (i < size - 1) { 
                    list.get(i).right = list.get(i + 1);
                }
                list.get(i).left = null;
            }
            // 因为是原地算法，所以这里需要赋值给原指针，root
            root = list.get(0);
        }

然后看到别的大神还有其他优秀的解法，不禁感叹，我还是太菜了哈…

其实基本上二叉树的算法题，都是 “遍历二叉树” 的变形，然后需要确认的就是采用递归还是非递归方法，最后结合相应题目要求应该就可以得出答案

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoaWppdWppdTMz_size_16_color_FFFFFF_t_70]: /images/20211015/05729509641c45caa8c29a16bd80b585.png