【二叉树进阶题目2】（算法题详细简介）

前言
5. 二叉树的层序遍历 ||（力扣107）
- 5.1 题目链接
- 5.2 示例分析
- 5.3 代码实现
6. 二叉树的层序遍历（力扣102)
- 6.1 题目链接
- 6.2 代码实现
7. 根据二叉树创建字符串（力扣606）
- 7.1 题目链接
- 7.2 示例分析
- 7.3 代码实现
8. 二叉树的最近公共祖先（力扣236）
- 8.1 题目链接
- 8.2 示例分析
- 8.3 代码实现

前言

下面是上一篇文章的链接，有需要的朋友们可以点击下方链接跳转呦~

【二叉树进阶题目1】（算法题详细简介）

下面是本文讲解的题目链接，大家可以先自己尝试一下，再看下文题解~

5. 二叉树的层序遍历 ||（力扣107）

6. 二叉树的层序遍历（力扣102)

7. 根据二叉树创建字符串（力扣606）

8. 二叉树的最近公共祖先（力扣236）

5. 二叉树的层序遍历 ||（力扣107）

5.1 题目链接

下面是题目链接：

5. 二叉树的层序遍历 ||（力扣107）

5.2 示例分析

由于返回类型为二位线性表，所以要先创建线性表
实现基本的层序遍历（用队列实现）
层序遍历的输出顺序是按照从下往上的顺序输出的（先储存后输出）

5.3 代码实现

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {

        // 创建一个二维链表
        List<List<Integer>> list = new ArrayList<>();
        // 普通的层序遍历
        // 创建一个队列
        Deque<TreeNode> deque = new ArrayDeque<>();
        while (root != null || !deque.isEmpty()) {
            while (deque.isEmpty()) {
                deque.offer(root);
            }

            int size = deque.size();
            // 创建一个一维链表
            List<Integer> l = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                // 队列中插入子树
                if (root.left != null)
                    deque.offer(root.left);
                if (root.right != null)
                    deque.offer(root.right);
                // 将目前队列中的数据存储到链表中
                l.add(deque.pop().val);
                root = deque.peek();
            }
            // 因为顺序为自下而上，所以为头插
            list.add(0, l);

        }
        return list;
    }
}

6. 二叉树的层序遍历（力扣102)

6.1 题目链接

这道题和上述题目相似，这道题是自上而下的方式输出，下面是题目链接，大家一起尝试一下吧。

6. 二叉树的层序遍历（力扣102)

6.2 代码实现

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
                List<List<Integer>> ret = new LinkedList<>();
        Deque<TreeNode> deque=new ArrayDeque<>();
        while(root!=null||!deque.isEmpty()){
            if(deque.isEmpty()){
                deque.push(root);
            }
            int size=deque.size();
            List<Integer> list=new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode t=new TreeNode(deque.pop().val);
                list.add(t.val);

                if(root.left!=null) deque.offer(root.left);
                if(root.right!=null) deque.offer(root.right);

                root=deque.peek();
            }
            ret.add(list);
        }
        return ret;
    }
}

7. 根据二叉树创建字符串（力扣606）

7.1 题目链接

点击下面链接开始做题吧！

7. 根据二叉树创建字符串（力扣606）

7.2 示例分析

本题的解决思路为子问题的方法

对比示例1和示例2，我们可以发现

当左子树不为空，右子树为空时，输出为“2（4）”
当左子树为空，右子树不为空时，输出“2（）（4）”
当左子树不为空，右子树不为空时，输出“2（4）（4）”
当左子树为空，右子树为空时，输出“2”

由于本题的输出为字符串，并且有频繁的插入操作，所以我们创建StringBuilder.

7.3 代码实现

class Solution {
 public String tree2str(TreeNode root) {
        if(root==null) return "";
        if(root.left==null&&root.right==null){
            return Integer.toString(root.val);
        }
        if(root.left!=null&&root.right==null){
            return new StringBuilder().append(root.val).append("(").append(tree2str(root.left)).append(")").toString();
        }
        return new StringBuilder().append(root.val).append("(").append(tree2str(root.left)).append(")(")
                .append(tree2str(root.right)).append(")").toString();

    }
}

8. 二叉树的最近公共祖先（力扣236）

8.1 题目链接

8. 二叉树的最近公共祖先（力扣236）

8.2 示例分析

以示例1的二叉树为例，讨论本题的多种情况：

第一种：在root的左右子树分别找到一个数，最近公共祖先为root
第二种：（这里可以有多种思路，我举一种思路的例子）
左子树找到一个数就直接返回，右子树没有找到数，说明两个数都在左子树，说明左子树找到的第一个数就是最近祖先
第三种：其中一个数等于root，root为最近祖先

8.3 代码实现

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null||root==p||root==q) return root;
        TreeNode left=lowestCommonAncestor(root.left,p,q);
        TreeNode right=lowestCommonAncestor(root.right,p,q);
        //对应上述3种情况
        if(left==null&&right==null) return null;
        if(left==null) return right;
        if(right==null) return left;
        return root;
    }