秋招力扣Hot100刷题总结——二叉树

二叉树相关的题目基本上都会使用递归，因此做二叉树的题目时首先使用递归，明确递归结束的条件。

1.二叉树的层序遍历 题目链接

• 题目要求：给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
  
• 代码及思路
  • 使用队列存储每一层的节点，左边节点先入队，右边节点后入队
  • 代码

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res=new ArrayList<>();
        if(root==null)return res;
        Queue<TreeNode> cache=new LinkedList<>();
        cache.offer(root);
        while(!cache.isEmpty()){
            int l=cache.size();
            List<Integer> temp=new ArrayList<>();
            for(int i=0;i<l;i++){
                TreeNode nd=cache.poll();
                temp.add(nd.val);
                if(nd.left!=null)cache.offer(nd.left);
                if(nd.right!=null)cache.offer(nd.right);
            }
            res.add(temp);
        }
        return res;
    }
}

2. 二叉树的最近公共祖先（字节客户端一面） 题目链接

• 题目要求：给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
  百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
  
• 代码及思路
  • 如果一个节点是 p 和 q 的祖先，那么 p 和 q 必须分别在这个节点的左右子树中，或者其中一个就是这个节点本身
  • 从根节点开始递归：如果当前节点是 null，直接返回 null，表示没有找到 p 或 q；如果当前节点是 p 或 q，那么直接返回当前节点；递归地在左子树中寻找 p 和 q；递归地在右子树中寻找 p 和 q
  • 合并递归条件，若左右子树都不为空则返回根节点；若都为空则返回空；若其中一个不为空，则返回不为空的
  • 代码

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==p||root==q)return root;
        if(root==null)return null;
        TreeNode l=lowestCommonAncestor(root.left,p,q);
        TreeNode r=lowestCommonAncestor(root.right,p,q);
        if(l!=null&&r!=null)return root;
        if(l==null&&r!=null)return r;
        if(l!=null&&r==null)return l;
        if(l==null&&r==null)return l;
        return null;
    }
}

3. 合并二叉树 题目链接

• 题目要求：给你两棵二叉树： root1 和 root2 。
  想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。
  返回合并后的二叉树。
  注意: 合并过程必须从两个树的根节点开始。
  
• 代码及思路
  • 本题使用递归，递归结束的条件是两棵树当前节点中有一个为空或者两个都为空
  • 每次递归的处理是将两棵树中对应的节点合并，然后递归合并一对左节点、一对右节点，同时将该节点的左右节点更新为合并后的左右节点
  • 代码

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1==null&&root2==null)return null;
        if(root1==null||root2==null)return root1==null?root2:root1;
        TreeNode newroot=new TreeNode(root1.val+root2.val);
        TreeNode newleft = mergeTrees(root1.left,root2.left);
        TreeNode newright = mergeTrees(root1.right,root2.right);
        newroot.left=newleft;
        newroot.right=newright;
        return newroot;
    }
}

4. 从前序与中序遍历序列构造二叉树 题目链接

• 题目描述：给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
  
• 代码及思路
  • 注意重构二叉树必须使用到中序遍历和前序后序其中一个的组合
  • 同样使用递归解决，每一次从前序遍历中找出根节点，然后根据根节点在中序遍历中的位置对数组进行拆分，分别构建左右子树
  • 拆分时可以使用一个hash来存储中序遍历中值和下标的对应关系
  • 代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    Map<Integer,Integer> cache=new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for(int i=0;i<inorder.length;i++){
            cache.put(inorder[i],i);
        }
        return build(preorder,0,preorder.length,inorder,0,inorder.length);
    }
    private TreeNode build(int[] preorder,int prebegin,int preend,int[] inorder,int inbegin,int inend){
        if(prebegin>=preend)return null;
        int index=cache.get(preorder[prebegin]);
        int nodeNum=index-inbegin;
        TreeNode root=new TreeNode(preorder[prebegin]);
        root.left=build(preorder,prebegin+1,prebegin+nodeNum+1,inorder,inbegin,inbegin+nodeNum);
        root.right=build(preorder,prebegin+1+nodeNum,preend,inorder,inbegin+nodeNum+1,inend);
        return root;
    }
}

5. 翻转二叉树 题目链接

• 题目要求：给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
  
• 代码及思路
  • 首先将根节点的左右子树交换，然后递归交换左右子树的孩子节点
  • 代码

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root==null)return root;
        if(root.left==null&&root.right==null)return root;
        TreeNode temp=root.left;
        root.left=root.right;
        root.right=temp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }
}

6.二叉树展开为链表 题目链接

• 题目要求：给你二叉树的根结点 root ，请你将它展开为一个单链表：
  展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
  展开后的单链表应该与二叉树 先序遍历 顺序相同。
  
• 代码及思路
  • 先递归分别展开左右子树，然后保留原右子树，并将右子树指向原左子树，原左子树指向null
  • 遍历root节点的右子树，知道最后一个节点，将最后一个节点的右指针指向原右子树
  • 代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public void flatten(TreeNode root) {
        if(root==null)return;
        if(root.left==null&&root.right==null)return;
        flatten(root.left);
        flatten(root.right);
        TreeNode temp=root.right;
        root.right=root.left;
        root.left=null;
        while(root.right!=null){
            root=root.right;
        }
        root.right=temp;
    }
}