LeetCode 154. 寻找旋转排序数组中的最小值 II-Js中文网

题目描述

难度：Hard

给定一个二叉树，其中所有的右节点要么是具有兄弟节点（拥有相同父节点的左节点）的叶节点，要么为空
将此二叉树上下翻转并将它变成一棵树，原来的右节点将转换成左叶节点。返回新的根。

例子:

输入: [1,2,3,4,5]

    1
   / \
  2   3
 / \
4   5

输出: 返回二叉树的根 [4,5,2,#,#,3,1]

   4
  / \
 5   2
    / \
   3   1
说明:

对 [4,5,2,#,#,3,1] 感到困惑? 下面详细介绍请查看 二叉树是如何被序列化的。

二叉树的序列化遵循层次遍历规则，当没有节点存在时，'#' 表示路径终止符。

这里有一个例子:

   1
  / \
 2   3
    /
   4
    \
     5
上面的二叉树则被序列化为 [1,2,3,#,#,4,#,#,5].

说明：

这道题是寻找旋转排序数组中的最小值
的延伸题目。
允许重复会影响算法的时间复杂度吗？会如何影响，为什么？
先自底向上，翻转二叉树，把子节点的 left，指向父节点
同时记录父节点有多少个子节点（0,1,2,）
把叶子节点加入队列
开始BFS，出队一个，就把该节点的 left （原来的父节点的子节点计数 -1）
当节点的子节点计数为0时，它就变成了叶子节点，可以入队了

/**
 * @param {number[]} nums
 * @return {number}
 */
class Solution {
    vector<vector<int>> ans;
    queue<TreeNode*> q;
    unordered_map<TreeNode*, int> map;//父节点底下挂着几个子节点
public:
    vector<vector<int>> findLeaves(TreeNode* root) {
        reverse(root);//上下翻转二叉树
        while(!q.empty())
        {
            int size = q.size(), i = 0;
            vector<int> lv(size);
            while(size--)
            {
                TreeNode *cur = q.front();
                q.pop();
                map[cur->left]--;//原父节点的子节点计数-1
                lv[i++] = cur->val;//当前值写入答案
                if(cur->left && map[cur->left]==0)//父节点计数为0，可以入队
                    q.push(cur->left);
            }
            ans.push_back(lv);
        }
        return ans;
    }
    TreeNode* reverse(TreeNode* root)
    {
        if(!root) return NULL;
        auto l = root->left;
        auto r = root->right;
        if(!l && !r)
            q.push(root);//叶子节点加入队列
        map[root] += (l?1:0) + (r?1:0);//记得加括号，子节点个数
        root->left = NULL;//断开子节点
        root->right = NULL;
        auto lc = reverse(l);
        auto rc = reverse(r);
        if(lc)
            lc->left = root;//子节点的left指向父节点
        if(rc)
            rc->left = root;
        return root;
    }
};