二叉树 part01

算法

LeetCode 144.二叉树的前序遍历

题目描述

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

示例

输入：root = [1,null,2,3]

输出：[1,2,3]

解释：

题目链接

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

解题思路

记住前序的输出顺序是根节点 - 左 - 右就不难解决, 迭代法需要使用栈来存储, 入栈顺序为根 - 右 - 左

递归法

class Solution {
    List<Integer> list = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        //前序，先输出节点，在输出左边然后是右边
        if(root == null)
            return list;
        list.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return list;
    }
}

迭代法

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

LeetCode 145.二叉树的后序遍历

题目描述

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

示例

输入：root = [1,null,2,3]

输出：[3,2,1]

解释：

题目链接

https://leetcode.cn/problems/binary-tree-postorder-traversal/description/

解题思路

记住前序的输出顺序是左 - 右- 根节点 就不难解决, 迭代法需要使用栈来存储, 入栈顺序为左 - 右 - 根

递归法

class Solution {
    List<Integer> list = new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root == null)
            return list;
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        list.add(root.val);
        return list;
    }
}

迭代法

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null){
            return result;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()){
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.left != null){
                stack.push(node.left);
            }
            if (node.right != null){
                stack.push(node.right);
            }
        }
        Collections.reverse(result);
        return result;
    }
}

LeetCode 94.二叉树的中序遍历

题目描述

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

示例

输入：root = [1,null,2,3]
输出：[1,3,2]

题目链接

https://leetcode.cn/problems/binary-tree-inorder-traversal/description/

解题思路

记住前序的输出顺序是左 - 根节点 - 右就不难解决, 迭代法略显麻烦, 但依旧采用栈来存储, 先需要往栈里存储所有的左节点, 直至为 null。然后出栈, 遍历右节点。

递归法

class Solution {
    List<Integer> list = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root == null)
            return list;
        inorderTraversal(root.left);
        list.add(root.val);
        inorderTraversal(root.right);
        return list;
    }
}

迭代法

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();  
        if(root == null)
            return result;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur != null || !stack.empty()){
            if(cur != null){
                stack.push(cur);
                cur = cur.left;
            }else{
                cur = stack.pop();
                result.add(cur.val);
                cur = cur.right;
            }
        }  
        return result;
    }
}

LeetCode 102.二叉树的层序遍历

题目描述

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

示例

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

题目链接

https://leetcode.cn/problems/binary-tree-level-order-traversal/description/

解题思路

迭代法

借助队列存储每一层的节点

开始时放入根节点到队列中
用 len记录每层节点的长度,
出队并赋值给 node, 将 node.val插入 list表中, list表记录每层的节点值
判断 node的左右节点是否为空, 不为空入队。
重复上面三步, 直至队列为空

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        while (!que.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int len = que.size();
            while (len-- > 0) {
                TreeNode node = que.poll();
                list.add(node.val);
                if (node.left != null) que.offer(node.left);
                if (node.right != null) que.offer(node.right);
            }
            res.add(list);
        }
        return res;
    }
}

LeetCode 107.二叉树的层次遍历 II

题目描述

给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。（即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）

示例

输入：root = [3,9,20,null,null,15,7]
输出：[[15,7],[9,20],[3]]

题目链接

https://leetcode.cn/problems/binary-tree-level-order-traversal-ii/description/

解题思路

反转上题的结果即可。有点愣了，没想到可以这么做

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);

        while (!que.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int len = que.size();

            while (len-- > 0) {
                TreeNode node = que.poll();
                list.add(node.val);
                if (node.left != null) que.offer(node.left);
                if (node.right != null) que.offer(node.right);
            }
            res.add(list);
        }
        Collections.reverse(res);
        return res;
    }
}

LeetCode 199.二叉树的右视图

题目描述

给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例

输入：root = [1,2,3,null,5,null,4]

输出：[1,3,4]

解释：

题目链接

https://leetcode.cn/problems/binary-tree-right-side-view/description/

解题思路

层序遍历, 然后取每层数组的最后一个。我这里用栈存每层节点，直接弹出栈顶就行了。

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        while (!que.isEmpty()) {
            Stack<Integer> stack = new Stack<>();
            int len = que.size();
            while (len-- > 0) {
                TreeNode node = que.poll();
                stack.push(node.val);
                if (node.left != null) que.offer(node.left);
                if (node.right != null) que.offer(node.right);
            }
            res.add(stack.pop());
        }
        return res;
    }
}

LeetCode 637.二叉树的层平均值

题目描述

给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。

示例

输入：root = [3,9,20,null,null,15,7]
输出：[3.00000,14.50000,11.00000]
解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
因此返回 [3, 14.5, 11] 。

题目链接

https://leetcode.cn/problems/average-of-levels-in-binary-tree/description/

解题思路

层序遍历, 每层求平均值

class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        while (!que.isEmpty()) {
            long sum = 0;
            int l = que.size();
            int len = que.size();
            while (len-- > 0) {
                TreeNode node = que.poll();
                sum += node.val;
                if (node.left != null) que.offer(node.left);
                if (node.right != null) que.offer(node.right);
            }
            res.add((1.0 * sum) / l);
        }
        return res;
    }
}

LeetCode 429.N叉树的层序遍历

题目描述

给定一个 N 叉树，返回其节点值的层序遍历。（即从左到右，逐层遍历）。

树的序列化输入是用层序遍历，每组子节点都由 null 值分隔（参见示例）。

示例

输入：root = [1,null,3,2,4,null,5,6]
输出：[[1],[3,2,4],[5,6]]

题目链接

https://leetcode.cn/problems/n-ary-tree-level-order-traversal/description/

解题思路

层序遍历中判断左右节点更改为一个循环, 判断所有的子节点是否为空

class Solution {
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) return res;
        Queue<Node> que = new LinkedList<>();
        que.offer(root);

        while (!que.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int len = que.size();
            while (len-- > 0) {
                Node node = que.poll();
                list.add(node.val);
                for (Node n : node.children) {
                    if (n != null) que.offer(n);
                }
            }
            res.add(list);
        }
        return res;
    }
}

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

题目描述

给定一棵二叉树的根节点 root ，请找出该二叉树中每一层的最大值。

示例

输入: root = [1,3,2,5,3,null,9]
输出: [1,3,9]

题目链接

https://leetcode.cn/problems/find-largest-value-in-each-tree-row/description/

解题思路

层序遍历, 设置哨兵，查找最大值

class Solution {
    public List<Integer> largestValues(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        while (!que.isEmpty()) {
            int Max = Integer.MIN_VALUE;
            int len = que.size();
            while (len-- > 0) {
                TreeNode node = que.poll();
                Max = Math.max(Max, node.val);
                if (node.left != null) que.offer(node.left);
                if (node.right != null) que.offer(node.right);
            }
            res.add(Max);
        }
        return res;
    }
}

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

题目描述

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

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

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

示例

输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化的输出按层序遍历排列，同一层节点由 next 指针连接，'#' 标志着每一层的结束。

题目链接

https://leetcode.cn/problems/populating-next-right-pointers-in-each-node/description/

解题思路

层序遍历, 用一个队列充当辅助队列记录每层节点, 每次出队判断是否还有要出的节点。没有就指向 null，否则指向队列首元素

class Solution {
    public Node connect(Node root) {
        Node cur = root;
        if (root == null) return root;
        Queue<Node> que = new LinkedList<>();
        que.offer(cur);

        while (!que.isEmpty()) {
            int len = que.size();
            while (len-- > 0) {
                Node node = que.poll();
                node.next = len == 0 ? null : que.peek();
                if (node.left != null) que.offer(node.left);
                if (node.right != null) que.offer(node.right);
            }
        }
        return root;
    }
}

LeetCode 117.填充每个节点的下一个右侧节点指针II

题目描述

给定一个二叉树：

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

填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。

初始状态下，所有 next 指针都被设置为 NULL。

示例

输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]
解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。序列化输出按层序遍历顺序（由 next 指针连接），'#' 表示每层的末尾。

题目链接

https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/description/

解题思路

同leetcode116

class Solution {
    public Node connect(Node root) {
        Node cur = root;
        if (root == null) return root;
        Queue<Node> que = new LinkedList<>();
        que.offer(cur);

        while (!que.isEmpty()) {
            int len = que.size();
            while (len-- > 0) {
                Node node = que.poll();
                node.next = len == 0 ? null : que.peek();
                if (node.left != null) que.offer(node.left);
                if (node.right != null) que.offer(node.right);
            }
        }
        return root;
    }
}

LeetCode 104.二叉树的最大深度

题目描述

给定一个二叉树 root ，返回其最大深度。

二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数

示例

输入：root = [3,9,20,null,null,15,7]
输出：3

题目链接

https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/

解题思路

层序遍历, 增加 depth记录层数

class Solution {
    public int maxDepth(TreeNode root) {
        int res = 0;
        Queue<TreeNode> que = new LinkedList<>();
        if (root != null) que.offer(root);
        while (!que.isEmpty()) {
            int len = que.size();
            while (len-- > 0) {
                TreeNode node =que.poll();
                if (node.left != null) que.offer(node.left);
                if (node.right != null) que.offer(node.right);
            }
            res++;
        }
        return res;
    }
}

LeetCode 111.二叉树的最小深度

题目描述

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

**说明：**叶子节点是指没有子节点的节点。

示例

输入：root = [3,9,20,null,null,15,7]
输出：2

题目链接

https://leetcode.cn/problems/minimum-depth-of-binary-tree/description/

解题思路

层序遍历, 只有当左右节点都为空时, 返回深度

class Solution {
    public int minDepth(TreeNode root) {
        int res = 0;
        Queue<TreeNode> que = new LinkedList<>();
        if (root != null ) que.offer(root);
        while (!que.isEmpty()) {
            int len = que.size();
            res++;
            while (len-- > 0) {
                TreeNode node = que.poll();
                if (node.left == null && node.right == null) return res;
                if (node.left != null) que.offer(node.left);
                if (node.right != null) que.offer(node.right);
            }
        }
        return res;
    }
}

递归法

class Solution {
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        return (left == 0 || right == 0) ? left + right + 1 : Math.min(left, right) + 1;
    }
}

如果觉得文章对你有用，请随意赞赏

算法训练营

二叉树 part01

https://pengxiang.space/archives/%E4%BA%8C%E5%8F%89%E6%A0%91-part01

作者

孤舟未系

发布于

2025/10/21 16:57

更新于

2025/10/21 16:57

许可协议

CC BY 4.0

二叉树 part01

LeetCode 144.二叉树的前序遍历

LeetCode 145.二叉树的后序遍历

LeetCode 94.二叉树的中序遍历

LeetCode 102.二叉树的层序遍历

LeetCode 107.二叉树的层次遍历 II

LeetCode 199.二叉树的右视图

LeetCode 637.二叉树的层平均值

LeetCode 429.N叉树的层序遍历

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

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

LeetCode 117.填充每个节点的下一个右侧节点指针II

LeetCode 104.二叉树的最大深度

LeetCode 111.二叉树的最小深度

作者

发布于

更新于

许可协议

评论