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

未完待续…