二叉树 --面试经典150题

tobegold574 Lv5
  2024-12-25 10:45:30 2024-12-25 10:45:30 Created   2024-12-30 14:47:59 2024-12-30 14:47:59 Updated    

相同的树(easy)

做题过程

不太记得了，反正就是选一个遍历方式一个一个比对，DFS或者BFS。

算法概述

原题

本题要求为比较两个树是否相同。

  • 时间复杂度为O(min(n,m))：不一样就是比完一棵较小的树就行
  • 空间复杂度为O(min(n,m))：递归

JAVA

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        } else if (p == null || q == null) {
            return false;
        } else if (p.val != q.val) {
            return false;
        } else {
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
    }
}

总结

先左再右或者先右再左都一样。要注意一开始要考虑递归到最底层（自底向上）的情况，然后才是false的情况。

从中序与后序遍历序列构造二叉树(medium)

做题过程

感觉和前序中序的那道题的思路还是差别蛮大的，还是不太会。

算法概述

原题

本题要求为如题所示。采用 递归 （迭代同理）。

  • 时间复杂度为O(n)
  • 空间复杂度为O(n)

JAVA

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
    // 全局变量用不用其实没关系，但是用了确实好一些
    int post_idx;
    int[] postorder;
    int[] inorder;

    // 中序遍历的映射关系
    Map<Integer, Integer> idx_map = new HashMap<Integer, Integer>();

    // 递归
    public TreeNode helper(int in_left, int in_right) {
        // 双指针相遇，结束
        if (in_left > in_right) {
            return null;
        }

        // 选择 post_idx 位置的元素作为当前子树根节点（后序遍历得到根节点位置）
        int root_val = postorder[post_idx];
        TreeNode root = new TreeNode(root_val);

        // 找到根节点在中序遍历中的位置
        int index = idx_map.get(root_val);

        // 下标减一，更新根节点（按照后序遍历顺序，进入右子树）
        post_idx--;
        // 先构造右子树
        root.right = helper(index + 1, in_right);
        // 再构造左子树
        root.left = helper(in_left, index - 1);
        return root;
    }

    public TreeNode buildTree(int[] inorder, int[] postorder) {
        this.postorder = postorder;
        this.inorder = inorder;
        // 从后序遍历的最后一个元素开始（整棵树的根节点）
        post_idx = postorder.length - 1;

        // 建立（元素，下标）键值对的哈希表
        int idx = 0;
        for (Integer val : inorder) {
            idx_map.put(val, idx++);
        }
        
        // 双指针初始指向中序遍历左右边界
        return helper(0, inorder.length - 1);
    }
}

总结

和前序遍历一样，后序遍历的意义主要在于 找到根节点 ，而中序遍历可以在定位根节点之后 快速找到左孩子和右孩子 ，重要的是当孩子不存在时，可以直接 通过缩小左右指针 ，判断出来这种情况，这是因为搭建过程是 自顶向下 的。

填充每个节点的下一个右侧节点指针 II(medium)

做题过程

我想的还是要用BFS，但是怎么组织代码结构来实现，还是没想出来。

算法概述

原题

本题要求为将每个节点的next指针指向它们同一层的右侧节点。模拟解决，但是算法可以更加巧妙。

  • 时间复杂度为O(n)
  • 空间复杂度为O(n)：可以通过技巧优化至O(1)

JAVA

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        // 标准BFS
        if(root==null) return root;
        Queue<Node> queue=new LinkedList<>();
        queue.offer(root);
        
        // 标准终止条件 
        while(!queue.isEmpty()){
             int size=queue.size();
            Node last=null;
            // 一直到队列为空，不用while是因为要处理root的情况
            for(int i=0;i!=size;++i){
                // 标准BFS
                Node n=queue.poll();
                if(n.left!=null) queue.offer(n.left);
                if(n.right!=null) queue.offer(n.right);
                // 按照队列内部顺序连接
                if(i!=0) last.next=n;
                // 用一个中间变量改变当前目标节点
                last=n;
            }
        }
        return root;
    }
}

总结

这道题主要考察的还是对迭代的理解，这里用到的是标准BFS的两个（可更改的）迭代特性：

  • 从左到右新增节点
  • 连接操作的次数正好跟迭代次数相同

还有一种降低空间复杂度的方法也是直接模拟，从上一层对下一层的next进行操作，这是额外将每层最右侧节点和下一层最左侧节点连接实现的，也就是一个变量指向即将连接的节点，另外一个节点指向，即将被连接节点的根节点。很巧妙。

路径总和(easy)

做题过程

以为直接照搬最简单的dfs就可以，结果感觉后面要回溯来了，还是对DFS的结构不熟悉。

算法概述

原题

本题要求为判断树中是否有路径总和为给定值的路径。DFS递归或DFS迭代。

  • 时间复杂度为O(n)：最坏
  • 空间复杂度为O(n)：栈

JAVA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return false; 
        }

        // 检查当前节点是否是叶子节点且满足路径和条件
        if (root.left == null && root.right == null) {
            return root.val == targetSum;
        }

        // 递归检查左右子树是否存在路径和为 targetSum - root.val 的路径
        int remainingSum = targetSum - root.val;
        return hasPathSum(root.left, remainingSum) || hasPathSum(root.right, remainingSum);
    }
}

总结

像这样直接对函数本题进行递归操作，而且有 条件就是参数 的情况下，应该考虑在递归中维护该条件对应的变量，通过递归改变此变量以及在函数内判断是否符合条件，而不是用全局变量维护。

如果是迭代，就是前缀和问题。

求根节点到叶节点数字之和(medium)

做题过程

用两个队列+BFS，然后打败4.85%，中间还让gpt改了冗余和错误的代码细节🤣，然后其实不是算法的问题，而是字符串处理的问题，我估计。

算法概述

原题

本题要求为计算所有自顶到底的路径总和的总和。

  • 时间复杂度为O(n)
  • 空间复杂度为O(n)

JAVA

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
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public int sumNumbers(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int sum = 0;
        // 一个BFS迭代队列
        Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
        // 一个路径总和队列
        Queue<Integer> numQueue = new LinkedList<Integer>();
        // 预处理根节点
        nodeQueue.offer(root);
        numQueue.offer(root.val);

        while (!nodeQueue.isEmpty()) {
            TreeNode node = nodeQueue.poll();

            // 这里用了剪枝
            int num = numQueue.poll();
            TreeNode left = node.left, right = node.right;
            // 如果没有左右子树，就直接加了，不用经过队列操作
            if (left == null && right == null) {
                sum += num;
                // 只有存在左右子树的情况还需要用队列维护
            } else {
                if (left != null) {
                    nodeQueue.offer(left);
                    // 这个比字符串操作快多了
                    numQueue.offer(num * 10 + left.val);
                }
                if (right != null) {
                    nodeQueue.offer(right);
                    numQueue.offer(num * 10 + right.val);
                }
            }
        }
        return sum;
    }
}

总结

当使用额外的数据结构来进行加减这种简单的关系时，应该需要考虑 是否可以用更简单的数据结构替代或者甚至不用数据结构 ，这也是一种优化的剪枝思路，即使复杂度相同，但是最终的运行结果却是完全不一样的。

二叉搜索树迭代器(medium)

做题过程

八分半，很标准很简单的一道题。

算法概述

原题

本题要求为给一棵树，提供按照中序遍历的顺序返回节点和判断节点是否存在的方法（类设计）。就是中序遍历，没别的。

  • 时间复杂度为O(n)：最长为O(n)，但按照操作数分摊就是O(1)
  • 空间复杂度为O(n)

JAVA

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
class BSTIterator {
    int p;
    List<Integer> nodes;

    public BSTIterator(TreeNode root) {
        nodes=new ArrayList<Integer>();
        p=0;
        inorder(nodes,root);
    }

    private void inorder(List<Integer> nodes,TreeNode root){
        if(root==null) return;
        inorder(nodes,root.left);
        nodes.add(root.val);
        inorder(nodes,root.right);
    }
    
    public int next() {
        return nodes.get(p++);
    }
    
    public boolean hasNext() {
        return p<nodes.size();
    }
}

总结

复习了一下中序遍历（先左，再添加节点，再右， 要背 ）。

完全二叉树的节点个数(easy)

做题过程

知道肯定可以剪枝或者优化什么的，但是没想出来，还是BFS，复杂度很差。

算法概述

原题

本题要求为如题所示。使用 二分查找和位运算 。

JAVA

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
// 先留个超简洁递归写法（DFS） 震惊🫨
class Solution {
    public int countNodes(TreeNode root) {
        return root==null?0:countNodes(root.left)+countNodes(root.right)+1;
    }
}

// 官方题解
class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int level = 0;

        // 找到最底层最靠左边的节点
        TreeNode node = root;
        while (node.left != null) {
            level++;
            node = node.left;
        }

        // low是最底层最左边节点的编号，high是最底层最右边节点的编号（1<<n就是2的n次方)
        int low = 1 << level, high = (1 << (level + 1)) - 1;

        // 标准二分查找
        while (low < high) {
            int mid = (high - low + 1) / 2 + low;
            if (exists(root, level, mid)) {
                low = mid;
            } else {
                high = mid - 1;
            }
        }
        return low;
    }

    public boolean exists(TreeNode root, int level, int k) {
        // 只是一个用于判断的辅助值（位数和从根节点到判断对象节点的操作个数一致）
        int bits = 1 << (level - 1);
        TreeNode node = root;
        while (node != null && bits > 0) {
            if ((bits & k) == 0) {
                node = node.left;
            } else {
                node = node.right;
            }
            // 更新操作数
            bits >>= 1;
        }
        return node != null;
    }
}

重要实例方法及属性(JAVA)

1 << n：这个就是2的n次方

总结

总而言之，就是按照完全二叉树的数组形式表示的情况下，每个节点都存在自己的编号，而 每个编号的二进制表示和它们所在层数的1 << (level - 1);的结果 通过 按位与 运算即可得到从根节点移动到该节点的路径，同时通过不断右移后者bits >>= 1;即可查找到下一次操作，本质上是完全二叉树的数组形式中父节点和子节点的下标关系。

背记 。

二叉树的层平均值(easy)

做题过程

BFS很好解决。

算法概述

原题

本题要求为计算树中每一层的平均值。

  • 时间复杂度为O(n)
  • 空间复杂度为O(n)

JAVA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    List<Double> ans=new ArrayList<>();
    public List<Double> averageOfLevels(TreeNode root) {
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size=queue.size();
            int p=size;
            double sum=0;
            while(p>0){
                TreeNode top=queue.poll();
                if(top.left!=null) queue.offer(top.left);
                if(top.right!=null) queue.offer(top.right);
                sum+=top.val;
                p--;
            }
            ans.add(sum/size);
        }
        return ans;
    }
}

总结

要注意浮点数提前设置double sum=0;，不然越界会有问题。

二叉树的锯齿形层序遍历(medium)

做题过程

根本懒得做，就是加个flag的问题。

算法概述

原题

本题要求为按照先左后右，再转为先右后左的顺序进行层序遍历。

  • 时间复杂度为O(n)
  • 空间复杂度为O(n)

JAVA

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
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new LinkedList<List<Integer>>();
        if (root == null) {
            return ans;
        }

        Queue<TreeNode> nodeQueue = new ArrayDeque<TreeNode>();
        nodeQueue.offer(root);
        // 多一个flag
        boolean isOrderLeft = true;

        while (!nodeQueue.isEmpty()) {
            Deque<Integer> levelList = new LinkedList<Integer>();
            int size = nodeQueue.size();
            for (int i = 0; i < size; ++i) {
                TreeNode curNode = nodeQueue.poll();
                // 这里用双端队列，可以选择从队头添加元素，或者队尾添加元素
                if (isOrderLeft) {
                    levelList.offerLast(curNode.val);
                } else {
                    levelList.offerFirst(curNode.val);
                }
                if (curNode.left != null) {
                    nodeQueue.offer(curNode.left);
                }
                if (curNode.right != null) {
                    nodeQueue.offer(curNode.right);
                }
            }
            ans.add(new LinkedList<Integer>(levelList));
            isOrderLeft = !isOrderLeft;
        }

        return ans;
    }
}

总结

还可以每一层加完了之后根据奇偶性使用Collections.reverse()。

二叉搜索树的最小绝对差(easy)

做题过程

虽然是easy，但是没思路怎么写这个递归。

算法概述

原题

本题要求为给出二叉搜索树（中序遍历结果为升序），计算任意两节点的最小绝对差（肯定是中序遍历中的相邻节点）。

  • 时间复杂度为O(n)
  • 空间复杂度为O(n)

JAVA

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
27
28
29
30
class Solution {
    int pre;
    // 另起一个变量作为被减数
    int ans;

    public int getMinimumDifference(TreeNode root) {
        ans = Integer.MAX_VALUE;
        // 一开始设置为哨兵值
        pre = -1;
        dfs(root);
        return ans;
    }

    public void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        // 遍历到左下
        dfs(root.left);
        if (pre == -1) {
            pre = root.val;
        } else {
            // 不用绝对值，因为是二叉搜索树
            ans = Math.min(ans, root.val - pre);
            pre = root.val;
        }
        // 标准中序遍历顺序
        dfs(root.right);
    }
}

总结

主要是理解中序遍历，总的来说应该是 先左，再操作，最后右 ，这个定式一定要牢记。还比较重要的是这里用pre来表示被减数，另设一个if判断处理它，但可以少写一个参量。

  • Title: 二叉树 --面试经典150题
  • Author: tobegold574
  • Created at : 2024-12-25 10:45:30
  • Updated at : 2024-12-30 14:47:59
  • Link: https://tobegold574.me/2024/12/25/二叉树-面试经典150题/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
二叉树 --面试经典150题
  1. 相同的树(easy)
    1. 做题过程
    2. 算法概述
    3. JAVA
    4. 总结
  2. 从中序与后序遍历序列构造二叉树(medium)
    1. 做题过程
    2. 算法概述
    3. JAVA
    4. 总结
  3. 填充每个节点的下一个右侧节点指针 II(medium)
    1. 做题过程
    2. 算法概述
    3. JAVA
    4. 总结
  4. 路径总和(easy)
    1. 做题过程
    2. 算法概述
    3. JAVA
    4. 总结
  5. 求根节点到叶节点数字之和(medium)
    1. 做题过程
    2. 算法概述
    3. JAVA
    4. 总结
  6. 二叉搜索树迭代器(medium)
    1. 做题过程
    2. 算法概述
    3. JAVA
    4. 总结
  7. 完全二叉树的节点个数(easy)
    1. 做题过程
    2. 算法概述
    3. JAVA
    4. 总结
  8. 二叉树的层平均值(easy)
    1. 做题过程
    2. 算法概述
    3. JAVA
    4. 总结
  9. 二叉树的锯齿形层序遍历(medium)
    1. 做题过程
    2. 算法概述
    3. JAVA
    4. 总结
  10. 二叉搜索树的最小绝对差(easy)
    1. 做题过程
    2. 算法概述
    3. JAVA
    4. 总结