博客

本篇文章Leetcode题目

Leetcode 226 翻转二叉树

Leetcode 116 填充每个节点的下一个右侧节点指针

Leetcode 114 二叉树展开为链表

刷二叉树的题关键在于框架，本质上我们得摸清楚遍历的情况。在做二叉树的时候，重点考虑两个方面。

第一

，以什么顺序进行遍历，无非就是前序、后序、中序、层序次序上的变种。对于递归函数的调用，我们严格按照函数给出

定义

去构建。不需要每次过分纠结在一层层递归中，把自己搞晕。因此，递归框架最有助于我们从全局上去分解问题。

第二

，明确在

当前

节点要做的事。当遍历到当前节点的时候，我是对它的孩子操作，还是说对节点本身有操作都需要理清楚。切忌把

手身的太长

，想不清楚层次关系，进行多余的操作。在当前层，只思考当前层的问题。

看题说话。

leetcode 226 翻转二叉树

思路：

1. 到了当前层，当前root位置，就交换左右子树。
2. 同样的步骤操作root->left，递归左子树。
3. 同样的步骤操作root->right，递归右子树。

实际上就是个前序遍历+当前节点操作为交换左右。

当遍历结束后，自然每个节点都经历以上三个步骤。完成全部翻转。

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root==NULL) return NULL;
        if(root->left==NULL&&root->right==NULL) return root;
        //当前节点操作：交换 
        TreeNode* tmp = new TreeNode;
        tmp = root->right;
        root->right = root->left;
        root->left = tmp;
        //递归左子树
        invertTree(root->left);
        //递归右子树
        invertTree(root->right);
        return root;
    }
};

leetcode 116 填充每个节点的下一个右侧节点指针

仔细考虑这道题需要两种next连接状态。

第一，同父节点的两个左右孩子相连

第二，不同父节点的孩子节点相连。

依照这个思路，我们需要构思对当前节点的操作来完成我们刚刚的两个要求。

有点难度的是在于第二个，应该怎么表示。

我一开始想的是很直观

root->left->right->next = root->right>left

很明显不靠谱，我的错误就在于没有把思维剥离出来，对着 当层节点。写出这个

错误关系

是还停留在要依靠一个父节点。事实情况是这样的吗？只要我们再多画一层子树，就知道问题在哪了。

所以第二种关系的链接，在于父子结点不同。那么我们怎么通过他们的关系，来进一步帮助我们呢？

对next！ 我们使用next将同父子的左右孩子相连，那么就可以很自然地表现出他们的后代。

也就是

    if(root->next)
    root->right->next = root->next->left;

因此前序遍历+当前节点操作（两种类型的链接），写出代码。

class Solution {
public:
    Node* connect(Node* root) {
        if(root==NULL) return NULL;
        if(root->left==NULL &&root->right==NULL) return root;
        if(root->left && root->right)
        root->left->next = root->right;
        if(root->next)
        root->right->next = root->next->left;
        connect(root->left);
        connect(root->right);
        return root;
    }
};

Leetcode 114 二叉树展开为链表

这道题我们思考的框架是啥呢。

函数

展开

的调用。

1.将左子树展开

2.将右子树展开.

3.把左子树接到右子树上。

所以这是后序遍历+当前操作（左子树接到右子树上）。

class Solution {
public:
    TreeNode* pre = NULL;
    void flatten(TreeNode* root) {
        if(root==NULL) return;
        flatten(root->right);
        flatten(root->left);

        // 存储节点
        TreeNode* left = root->left;
        TreeNode* right = root->right;

        //把左子树挂到右子树
        root->left = NULL;
        root->right = left;  

       //接着链接原来右子树
       while(root->right){
           root = root->right; 
       }
       root->right = right;
    }
};

既然可以想想刚刚那样左-右-根。如果我们先右-左-根会怎么样？

我们发现，按照

右-左-根

的顺序遍历节点，正好符合构成的链表从尾到头的顺序！ 那既然如此，咱们就根据当前的遍历节点，每次把节点依顺序插入不就好了吗？ 这里我们需要引入一个辅助的指针，来告诉我们当前插入到了链表的哪里。并且记得删除左子节点。这后面的过程其实就变成了一个链表插入的过程。

而不需要像原来一样需要记录原先右子树所在的位置，考虑左子树插入变动后还要重新定位新的位置。因此减少了复杂度。

class Solution {
public:
    TreeNode* pre = NULL;
    void flatten(TreeNode* root) {
        if(root==NULL) return;
        flatten(root->right);
        flatten(root->left);
        //从尾巴上开始向前插
        root->right = pre;
        root->left = NULL;
        pre = root;
    }
};

写在最后

仔细阅读，我们为三道题梳理的结果是。

• leetcode 226 翻转二叉树 = 前序遍历+当前节点操作为交换左右。
• leetcode 116 填充每个节点的下一个右侧节点指针 = 前序遍历+当前节点操作（两种类型的链接）
• Leetcode 114 二叉树展开为链表 = 后序遍历+当前节点操作（左子树接到右子树上 或 链接到链表上）