• leetcode面试题之二叉树

    文章目录

    144. 二叉树的前序遍历

    题目：给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

    链接：https://leetcode.cn/problems/binary-tree-preorder-traversal/

    思路:前序遍历：根左右

    1. 递归
    2. 非递归
      （1）栈
      （2）根节点先入栈，再是右节点入栈，再左节点

    代码：

    递归：

    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        preorder(root, res);
        return res;
    }

    public void preorder(TreeNode root, List<Integer> res) {
        if (root == null) return;
        res.add(root.val);
        preorder(root.left, res);
        preorder(root.right, res);
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    非递归：

    public List<Integer> preorderTraversal(TreeNode root) {
       Stack<TreeNode> st = new Stack<>();
       List<Integer> res = new ArrayList<>();
       if (root != null) st.push(root);
       while (!st.isEmpty()) {
           TreeNode node = st.pop();
           res.add(node.val);
           if (node.right != null) st.push(node.right);
           if (node.left != null) st.push(node.left);
       }
       return res;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    94. 二叉树的中序遍历

    题目：给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

    链接：https://leetcode.cn/problems/binary-tree-inorder-traversal/

    思路：中序：左根右
    非递归

    1. 根节点不为空，根节点入栈，并继续往左走
    2. 根节点为空，出栈并访问，继续往右走

    代码：

    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> st = new Stack<>();
        while (root != null || !st.isEmpty()) {
            // 根节点不为空，根节点入栈，继续往左走
            if (root != null) {
                st.push(root);
                root = root.left;
            }else {
                // 根节点为空，栈不为空，出栈访问，继续往右走
                root = st.pop();
                res.add(root.val);
                root = root.right;
            }
        }
        return res;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    145. 二叉树的后序遍历

    题目：给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

    链接：https://leetcode.cn/problems/binary-tree-postorder-traversal/

    思路：后序：左右根
    前序：根左右 —> 改为根右左 —> 再反转
    反转：Collections.reverse(res);

    代码：

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Stack<TreeNode> st = new Stack<>();
        // 前序：根左右  ---> 根右左
        if (root != null) st.push(root);
        while (!st.isEmpty()) {
            TreeNode node = st.pop();
            res.add(node.val);
            if (node.left != null) st.push(node.left);
            if (node.right != null) st.push(node.right);
        }
        // 反转 根右左 ---> 左右根
        Collections.reverse(res);
        return res;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    102. 二叉树的层序遍历

    题目：给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）

    链接：https://leetcode.cn/problems/binary-tree-level-order-traversal/

    思路：层次遍历：队列

    代码：

    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> q = new ArrayDeque<>();
        // 1. 处理根节点
        if (root != null) q.add(root);
        // 2.遍历每层
        while (!q.isEmpty()) {
            int n = q.size(); // 记录当层节点数
            List<Integer> level = new ArrayList<>(); // 记录当层节点值
            // 处理当层节点：1.出栈并访问 2.左节点入队 3.右节点入队 
            for (int i = 0; i < n; i ++) {
                TreeNode node = q.poll();
                level.add(node.val);
                if (node.left != null) q.add(node.left);
                if (node.right != null) q.add(node.right);
            }
            res.add(level);
        }
        return res;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    层次遍历其他题目

    107. 二叉树的层序遍历 II

    题目：自底向上的层序遍历

    链接：https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/
    思路：层次遍历，最后反转结果

    代码：

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> q = new ArrayDeque<>();
        if (root != null) q.add(root);
        while (!q.isEmpty()) {
            int n = q.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < n; i ++) {
                TreeNode node = q.poll();
                level.add(node.val);
                if (node.left != null) q.add(node.left);
                if (node.right != null) q.add(node.right);
            }
            res.add(level);
        }
        // 反转
        Collections.reverse(res);
        return res;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    199. 二叉树的右视图

    题目：给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
    链接：https://leetcode.cn/problems/binary-tree-right-side-view/
    思路：层次遍历，记录每层的最后一个节点值

    代码：

    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Queue<TreeNode> q = new ArrayDeque<>();
        if (root != null) q.add(root);
        while (!q.isEmpty()) {
            int n = q.size();
            for (int i = 0; i < n; i ++) {
                TreeNode node = q.poll();
                // res记录每层的最后一个节点
                if (i == n - 1) res.add(node.val);
                if (node.left != null) q.add(node.left);
                if (node.right != null) q.add(node.right);
            }
        }
        return res;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    637. 二叉树的层平均值

    题目：给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
    链接：https://leetcode.cn/problems/average-of-levels-in-binary-tree/
    思路：层次遍历，每层遍历时，求得节点的sum，一层遍历完成后取平均

    代码：

    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> res = new ArrayList<>();
        Queue<TreeNode> q = new ArrayDeque<>();
        if (root != null) q.add(root);
        while (!q.isEmpty()) {
            int n = q.size(); 
            double sum = 0; // 每层节点求和
            List<Integer> level = new ArrayList<>(); 
            for (int i = 0; i < n; i ++) {
                TreeNode node = q.poll();
                sum += node.val;
                if (node.left != null) q.add(node.left);
                if (node.right != null) q.add(node.right);
            }
            // 节点值和去平均后放入res
            res.add(sum / n);
        }
        return res;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    429. N 叉树的层序遍历

    题目：给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）
    树的序列化输入是用层序遍历，每组子节点都由 null 值分隔
    链接：https://leetcode.cn/problems/n-ary-tree-level-order-traversal/
    思路：层次遍历

    代码：

    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> res = new ArrayList<>();
        Queue<Node> q = new ArrayDeque<>();
        if (root != null) q.add(root);
        while (!q.isEmpty()) {
            int n = q.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < n; i ++) {
                Node node = q.poll();
                level.add(node.val);

                // N叉树 遍历入队
                List<Node> children = node.children;
                for (Node child : children) {
                    if (child != null) q.add(child);
                }
            }
            res.add(level);
        }
        return res;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21

    515. 在每个树行中找最大值

    题目：给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值
    链接：https://leetcode.cn/problems/find-largest-value-in-each-tree-row/
    思路：层次遍历

    代码：

    public List<Integer> largestValues(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Queue<TreeNode> q = new ArrayDeque<>();
        if (root != null) q.add(root);
        while (!q.isEmpty()) {
            int n = q.size(), max = Integer.MIN_VALUE;
            for (int i = 0; i < n; i ++) {
                TreeNode node = q.poll();
                max = Math.max(max, node.val);
                if (node.left != null) q.add(node.left);
                if (node.right != null) q.add(node.right);
            }
            res.add(max);
        }
        return res;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

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

    题目：给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点

    struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。初始状态下，所有 next 指针都被设置为 NULL
    链接：https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/
    思路：层次遍历

    ​ LinkedList，处理本层第一个节点、非第一个节点、最后一个节点方法不同

    代码：

    只能使用常量级额外空间
    思路简单，但不满足题目条件

    public Node connect(Node root) {
        LinkedList<Node> q = new LinkedList<>();
        if (root == null) return root;
        q.add(root);
        while(!q.isEmpty()) {
            int n = q.size();
            // 将队列中的元素串联起来
            Node node = q.get(0);
            for (int i = 1; i < n; i ++) {
                node.next = q.get(i);
                node = q.get(i);
            }
            // 遍历每个节点并入队
            for (int i = 0; i < n; i ++) {
                node = q.remove();
                if (node.left != null) q.add(node.left);
                if (node.right != null) q.add(node.right);
            }
        }
        return root;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    public Node connect(Node root) {
        Queue<Node> q = new LinkedList<>();
        if (root != null) q.add(root);
        while (!q.isEmpty()) {
            int n = q.size();
            Node node = null;
            Node nodePre = null;
            for (int i = 0; i < n; i ++) {
                // 本层第一个节点
                if (i == 0) {
                    node = q.poll();
                    nodePre = node;
                } else {
                    // 本层非第一个节点
                    node = q.poll();
                    nodePre.next = node;
                    nodePre = nodePre.next;
                }
                if (node.left != null) q.add(node.left);
                if (node.right != null) q.add(node.right);
            }
            // 本层最后一个节点
            nodePre.next = null;
        }
        return root;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    104. 二叉树的最大深度

    题目：给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。
    链接：https://leetcode.cn/problems/maximum-depth-of-binary-tree/
    思路：

    层次遍历
    递归

    代码：

    层次遍历：

    public int maxDepth(TreeNode root) {
        int depth= 0;
        Queue<TreeNode> q = new LinkedList<>();
        if (root != null) q.add(root);
        while (!q.isEmpty()) {
            int n = q.size();
            for (int i = 0; i < n; i ++) {
                TreeNode node = q.poll();
                if (node.left != null) q.add(node.left);
                if (node.right != null) q.add(node.right);
            }
            depth ++;
        }
        return depth;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    递归：

    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        else {
            int left = maxDepth(root.left);
            int right = maxDepth(root.right);
            return Math.max(left, right) + 1;
        }
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    111. 二叉树的最小深度

    题目：给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。说明：叶子节点是指没有子节点的节点
    链接：https://leetcode.cn/problems/minimum-depth-of-binary-tree/
    思路：层次遍历：当遍历到左右孩子都为空时，说明到达最低点

    代码：

    递归：

    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        // 注意是根节点到叶子节点
        // 比如：如果根节点没有左子树，有右子树，最小深度不为1
        if (root.left != null && root.right == null) {
            return 1 + minDepth(root.left);
        }
        if (root.left == null && root.right != null) {
            return 1 + minDepth(root.right);
        }
        return 1 + Math.min(minDepth(root.left), minDepth(root.right));
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12

    层次遍历：

    public int minDepth(TreeNode root) {
        int depth = 0;
        Queue<TreeNode> q = new LinkedList<>();
        if (root != null) q.add(root);
        while (!q.isEmpty()) {
            int n = q.size();
            depth ++;
            for (int i = 0; i < n; i ++) {
                root = q.poll();
                // 当左右孩子都为空时，说明遍历到最低点
                if (root.left == null && root.right == null) {
                    return depth;
                }
                if (root.left != null) q.add(root.left);
                if (root.right != null) q.add(root.right);
            }
        }
        return depth;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    559. N 叉树的最大深度

    题目：给定一个 N 叉树，找到其最大深度。最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔
    链接：https://leetcode.cn/problems/maximum-depth-of-n-ary-tree/
    思路：类似于二叉树的最大深度
    1.递归法
    2.迭代法（层次遍历）

    代码：

    递归

    public int maxDepth(Node root) {
        int depth = 0;
        if (root == null) return depth;
        for (Node child : root.children){
            depth = Math.max(depth, maxDepth(child));
        }
        return depth + 1;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    层次遍历

    public int maxDepth(Node root) {
        int depth = 0;
        Queue<Node> q = new LinkedList<>();
        if (root != null) q.add(root);
        while (!q.isEmpty()) {
            int n = q.size();
            depth ++;
            for (int i = 0; i < n; i ++) {
                Node node = q.poll();
                for (Node child : node.children) {
                    if (child != null) q.add(child);
                }
            }
        }
        return depth;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    226. 翻转二叉树

    题目：给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
    链接：https://leetcode.cn/problems/invert-binary-tree/
    思路：遍历时翻转每个节点的左右子节点，前序、后序、层次都可以，中序要注意避免左右节点翻转两次

    代码：层次

    public TreeNode invertTree(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        if (root != null) q.add(root);
        while (!q.isEmpty()) {
            int n = q.size();
            for (int i = 0; i < n; i ++) {
                TreeNode node = q.poll();
                swap(node);
                if (node.left != null) q.add(node.left);
                if (node.right != null) q.add(node.right);
            }
        }
        return root;
    }

    public void swap(TreeNode node) {
        TreeNode tmp = node.left;
        node.left = node.right;
        node.right = tmp;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    101. 对称二叉树

    题目：给你一个二叉树的根节点 root ， 检查它是否轴对称。
    链接：https://leetcode.cn/problems/symmetric-tree/
    思路
    递归：判断节点为空、不为空的情况；不为空时判断节点值是否相同
    注意比较对象：
    1.左子树的左节点<=>右子树的右节点
    2.左子树的右节点<=>右子树的左节点

    代码：

    递归

    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return compare(root.left, root.right);
    }

    boolean compare(TreeNode left, TreeNode right) {
        // 判断节点为空的情况
        if (left == null && right != null) return false;
        else if (left != null && right == null) return false;
        else if (left == null && right == null) return true;
        // 判断节点不为空的情况
        else if (left.val != right.val) return false;
        // 节点不为空，且节点值相等，递归遍历
        else return compare(left.left, right.right) && compare(left.right, right.left);
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    迭代：

    public boolean isSymmetric(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        if (root == null) return true;
        q.add(root.left);
        q.add(root.right);
        while (!q.isEmpty()) {
            TreeNode leftNode = q.poll(), rightNode = q.poll();
            if (leftNode == null && rightNode == null) continue;
            // false情况合集
            if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) return false;
            q.add(leftNode.left);
            q.add(rightNode.right);
            q.add(leftNode.right);
            q.add(rightNode.left);
        }
        return true;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    未完待续…

  • 相关阅读:
    电脑录屏快捷键，轻松提升录屏效率
    三、react组件的生命周期
    CSS旋转、缩放、渐变
    【计算机组成原理】计算机系统概述 —— 计算机硬件组成与性能指标
    String方法：分割、梦回C语言，格式化输出format
    npm、pnpm和yarn【简单了解】
    vue.js毕业设计，基于vue.js前后端分离订座预约系统（H5移动项目） 开题报告
    基于JAVA的RSA文件加密软件的设计与实现
    汽车服务门店小程序模板制作指南
    Scratch、Python、C++，谁才是少儿编程的第一选择？
  • 原文地址：https://blog.csdn.net/mys_mys/article/details/128194465