Binary Tree Upside Down LC解题记录

Shonim 发布于2019-08-14 14:21 / 2680人阅读

摘要：题目内容因为这道题被锁住了，在写这篇文章时还有天就要过期了，把原题也贴上来。题目要求，树的结构是每个当右边子节点的，它肯定有个，就是它的根节点肯定有个左边子节点，也就是说它是二胎。递归设置终止条件，在空节点或最左边的叶子处终止。

题目内容

Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root.

For example:
Given a binary tree {1,2,3,4,5},
    1
   / 
  2   3
 / 
4   5
return the root of the binary tree [4,5,2,null,null,3,1].
   4
  / 
 5   2
    / 
   3   1

（因为这道题被锁住了，在写这篇文章时还有23天就要过期了，把原题也贴上来。）题目要求，树的结构是每个当右边子节点的，它肯定有个sibling，就是它的根节点肯定有个左边子节点，也就是说它是二胎。现在要把这个树从右往左看，要返回新的树。

解决思路

这道题有点儿类似反转链表，所以需要逐个修改每个节点的指向，以前的爷爷可能就是明天的孙子，曾经在工科专业成绩优秀转到CS重头再来也是这个心情。再仔细看，对于1->2->4，想逆转成4->2->1，其实就是左<-根->右变成了右<-左->根，好的办法是先找到左，然后开倒车，想办法把根和右的关系调整过来。
所以这道题用到自下而上递归的办法，先找到最左边的叶子，作为新的root，然后给新的root分配好它的left，right child。比如这个例子，先搞清楚4，5，2三个节点的关系，然后再向上找，搞1，2，3之间的关系。

两个需要注意的地方，一个是如何高效的找到4，也就是最左边的叶子。利用好递归方法的返回值，总会返回最小规模问题的返回值，也就是说，当递归终止时的返回值就是整个递归方法的返回值，之前这句话讲的很绕，我自己也在理解中。
第二，注意把原来根节点和两个子节点的指针删掉，因为最后原来的根节点一定会被变成一个叶子节点，那么叶子节点还指着根节点的话，就是个漂亮的环，会出现stackoverflow的错误。

code

public class Solution {
    public TreeNode upsideDownBinaryTree(TreeNode root) {
        //递归设置终止条件，在空节点或最左边的叶子处终止。
        if(root == null || (root.left == null && root.right == null)) return root;
        //把最左边的叶子拎出来作为新的root，留着返回
        TreeNode newRoot = upsideDownBinaryTree(root.left);
        //改各个节点之间的关系
        root.left.left = root.right;
        root.left.right = root;
        //这步非常有必要，每次改完之后把原来的节点关系都清空，否则成环
        root.left = null;
        root.right = null;
        
        return newRoot;
    }
}

复杂度分析

程序遍历了所有的节点，而且每个节点算是遍历两次，一次从上到下，一次从下到上。复杂度是O(n)。

GPU云服务器云服务器 binary-tree binary-search-tree Upside 解题思路

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64962.html

LeetCode 156 Binary Tree Upside Down 上下翻转二叉树

摘要：翻转以后如下解题思路翻转的形式一开始不是很清楚，但是里面的高票答案给了一个很好的解释。看例子，树的左边最深的底层是，是新的。对于每个，将链接右孩子的指针去掉，将变为当前左孩子的，成为左孩子的。递归的写法递归调用得到新的，并且沿途改变结构。 LeetCode 156 Binary Tree Upside Down Given a binary tree where all the rig...

Loong_T 2019-08-16 13:28 评论0 收藏0
Strobogrammatic Number 系列 LC解题记录（未完成）

摘要：所以这题先建立一个对应的，然后扫一遍字符串就可以了。复杂度分析第二题题目内容解决思路一看关键词，通常都是，深搜一遍，挖地三尺，雁过拔毛。复杂度分析第三题题目内容解决思路复杂度分析该系列共三道题，Company Tag只有一个Google，那就必须要做了。第一题题目内容 A strobogrammatic number is a number that looks the same ...

王晗 2019-08-14 14:23 评论0 收藏0
[Leetcode-Tree]Maximum / Minimum Depth of Binary T

摘要：解题思路用递归实现很简单，对于每个根节点，最大深度就等于左子树的最大深度和右子树的最大深度的较大值。解题思路本题的注意点在于如果某个根节点有一边的子树为空，那么它的深度就等于另一边不为空的子树的深度，其他的逻辑与上一题相同。 Maximum Depth of Binary TreeGiven a binary tree, find its maximum depth. The maxi...

Thanatos 2019-08-16 10:26 评论0 收藏0
LeetCode 104 Maximum Depth of Binary Tree 二叉树最大深度

LeetCode 104 Maximum Depth of Binary Tree难度：Easy 题目描述：找到一颗二叉树的最深深度。Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down ...

PiscesYE 2019-08-16 13:28 评论0 收藏0
leetcode 315 Count of Smaller Numbers After Self 以

摘要：题目意思就是要一个个的返回当前的最小值。所以解法自然就是。我们需要找出被打乱的点并返回正确结果。然后将两个不正确的点记录下来，最后回原来正确的值。如果是叶子节点，或者只有一个子树。思想来自于的代码实现。跳过总结请点这里：https://segmentfault.com/a/11... BST最明显的特点就是root.left.val < root.val < root.right.v...

inapt 2019-08-14 17:20 评论0 收藏0