第零章：手把手带你刷二叉树(第一期)

labuladong 手把手带你刷二叉树（第一期）

递归算法的关键要明确函数的定义，相信这个定义，而不要跳进递归细节
递归结束的条件一定要写，否则递归跳不出来
写二叉树的算法题，都是基于递归框架的（只要涉及递归，都可以抽象成二叉树的问题），我们先要搞清楚 root 节点它自己要做什么，然后根据题目要求选择使用前序，中序，后续的递归框架

226. 翻转二叉树

• 相当于前序遍历，把当前的左右节点进行翻转，再将左右子树进行递归

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def invertTree(self, root):
        """
        :type root: TreeNode
        :rtype: TreeNode
        """
        if not root:
            return

        root.left,root.right=root.right,root.left
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if (root==nullptr) return root;
        TreeNode* tmp=root->left;
        root->left= root->right;
        root->right= tmp;
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
};

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

• 若只对一个节点进行操作，则不能把不同子树的左右节点连接。因此在递归函数中，把函数的参数增加到2个，并对这两个节点进行操作
• 用一个帮助函数connectTwoNode()对两个“子根”节点进行操作，以便相邻树的左右节点也能连接

"""
# Definition for a Node.
class Node(object):
    def __init__(self, val=0, left=None, right=None, next=None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution(object):
    def connect(self, root):
        """
        :type root: Node
        :rtype: Node
        """
        def connectTwoNode(node1,node2):
            # if node1==None or node2==None:
            if not (node1 and node2):
                return 
            node1.next=node2
            connectTwoNode(node1.left,node1.right)
            connectTwoNode(node2.left,node2.right)
            connectTwoNode(node1.right,node2.left) #相邻树的左右节点相连

        if not root: return None
        connectTwoNode(root.left,root.right)# 当前的两个“子根”节点相连
        return root

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;
    Node() : val(0), left(NULL), right(NULL), next(NULL) {}
    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
//    辅助函数不返回内容，只对节点进行操作
    void connectTwoNode(Node *node1, Node *node2) {
        if (node1 == nullptr && node2 == nullptr) return;
        node1->next = node2;
        connectTwoNode(node1->left, node1->right);
        connectTwoNode(node2->left, node2->right);
        connectTwoNode(node1->right, node2->left);
    }

    Node *connect(Node *root) {
        if (root == nullptr) return root;
        connectTwoNode(root->left, root->right);
        return root; // 对节点进行操作后，返回root根节点
    }
};

114. 二叉树展开为链表

• 相当于后续遍历，先把左右子树拉平，再对根节点进行操作

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def flatten(self, root):
        """
        :type root: TreeNode
        :rtype: None Do not return anything, modify root in-place instead.
        """
        # 递归结束的条件
        if root ==None:return
        # 后续遍历，把左右子树拉平
        l=self.flatten(root.left)
        r=self.flatten(root.right)
        # 将root原来的左子树置空，并将拉平的左子树接到右子树上
        root.left=None
        root.right=l
        # 将拉平的右子树接到当前右子树的末端
        p=root
        while p.right!=None: 
            p=p.right # 将p置到root头上，并一直跳到末端
        p.right=r # 末端接拉平的右子树
        return root

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void flatten(TreeNode* root) {
        if (root==nullptr) return ;
        // 后序遍历：左，右
        flatten(root->left);
        flatten(root->right);
        // 用两个节点记录递归后的结果
        TreeNode* l=root->left;
        TreeNode* r=root->right;
        // 左变置空，把左边的结果放到右边
        root->left=nullptr;
        root->right=l;
        // 找到末尾，并把右边的结果拼接到末尾
        TreeNode*p =root;
        while(p->right!=nullptr){
            p=p->right;
        }
        p->right=r;
    }
};