刷题日记Day1 | 二叉树

写树相关的算法，简单说就是，先搞清楚当前 root 节点「该做什么」以及「什么时候做」，然后根据函数定义递归调用子节点，递归调用会让孩子节点做相同的事情。

• • 226.翻转二叉树
  • 116.填充二叉树每个节点的右侧指针
  • 114.将二叉树展开为链表

分析：

• 当前节点需要做什么？
  交换左右子节点。

• 什么时候做？
  前序遍历 或 后序遍历的时候。

解答：

class Solution {
    public TreeNode invertTree(TreeNode root) {
        //base case
        if(root == null){return null;}

        //交换左右节点
        TreeNode tmp = root.right;
        root.right = root.left;
        root.left = tmp;

        //左右孩子继续翻转
        invertTree(root.left);
        invertTree(root.right);

        return root;

    }
}

分析：
题目的意思就是把二叉树的每一层节点都用 next 指针连接起来。
再把问题细化——把二叉树左右相邻的两个节点连起来
这时候就发现有两种不同的情况：
1.相邻的左右节点属于同一个父节点。
2.相邻的左右节点属于不同的父节点。

解答：

class Solution {
    public Node connect(Node root) {
        //base case
        if(root == null){return null;}
        //连接两个相邻节点
        connectTwoNode(root.left , root.right);
        return root;
    }
    
    public void connectTwoNode(Node node1,Node node2){
        if(node1 == null || node2 == null){return;} 
        //连接两个节点
        node1.next = node2;
        //连接相同父节点的两个节点
        connectTwoNode(node1.left,node1.right);
        connectTwoNode(node2.left,node2.right);
        //连接不相同父节点的两个节点
        connectTwoNode(node1.right,node2.left);
    }
}

分析：
本题的核心是传入一个root根节点，以root为根的二叉树会被拉成一条链表。
在分成小问题就是把root的右节点接到左节点下，然后将左子树作为右子树。

解答：

class Solution {
    public void flatten(TreeNode root) {
        //base case
        if(root == null){return;}

        //拉伸左右子树，不用关心具体递归细节。
        flatten(root.left);
        flatten(root.right);

        //用两个变量把原来的左右子树存起来
        TreeNode left = root.left;
        TreeNode right = root.right;

        //将左子树作为右子树
        root.left = null;
        root.right = left;

        //将原先右子树接到当前右子树的末端,p==原先的根节点
        TreeNode p = root;
        while(p.right != null){
            p = p.right;
        }
        p.right = right;
        
    }
}