对称的二叉树

剑指 Offer 28. 对称的二叉树 - 力扣（Leetcode）

题目要求

请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
    1

   / \

  2   2

 / \ / \

3  4 4  3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
    1

   / \

  2   2

   \   \

   3    3

例子：

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

提示：

0 <= 节点个数 <= 1000

思路分析

在递归的条件下：

  1. 根节点是否相等；
  2. 判断树的左子树的左子节点和右子树右子节点是否相等；
  3. 判断树的左子树的右子节点和右子树左子节点是否相等；

代码实现

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        // 判断树是否为空或只有一个节点
        if(root == null || (root.left == null && root.right == null)){
            return true;
        }
        // 判断它左右子树是否互为镜像二叉树
        return f(root.left,root.right);
    }
    public boolean f(TreeNode A,TreeNode B){
        // 判断左右子树是否都为空
        if(A == null && B == null){
            return true;
        }
        // 判断左右子树其中一个是否为空
        if(A == null || B == null){
            return false;
        }
        // 左右子树是否不相等
        if(A.val != B.val){
            return false;
        }
        // 递归判断A的左子树和B的右子树 与 A的右子树和B的左子树
        // 是否为镜像二叉树
        return f(A.left,B.right) && f(A.right,B.left);
    }
}

顺时针打印矩阵

剑指 Offer 29. 顺时针打印矩阵 - 力扣（Leetcode）

题目要求

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

例子：

1
2
3
4
5
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]
    
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

提示：

  • 0 <= matrix.length <= 100
  • 0 <= matrix[i].length <= 100

思路分析

image-20221217115841309

  • 规定打印方向：右->下->左->上；
  • 每次向右遍历后，top向下移动：top++;
  • 每次向下遍历后，right向左移动：right–；
  • 每次向左遍历后，bottom向上移动：bottom–;
  • 每次向上遍历后，left向右移动：left++;
  • 每次移动后需要判断是否遍历完毕；

代码实现

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
class Solution {
    public int[] spiralOrder(int[][] matrix) {
        // 判断特殊情况
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return new int[0];
        }
        // 定义上下左右
        int l = 0;
        int r = matrix[0].length-1;
        int t = 0;
        int b = matrix.length-1;
        // 定义一个以为数组
        int[] res = new int[(r+1) * (b+1)];
        int k =0;
        while(true){
            // 从左向右遍历
            for(int i=t,j=l;j<=r;j++){
                res[k++] = matrix[i][j];
            }
            // top 向下移动
            t++;
            // 判断是否遍历完毕
            if(t>b) break;
            // 从上向下遍历
            for(int i=t,j=r;i<=b;i++){
                res[k++] = matrix[i][j];
            }
            // right 向左移动
            r--;
            // 判断是否遍历完毕
            if(r<l) break;
            // 从右向左遍历
            for(int i=b,j=r;j>=l;j--){
                res[k++] = matrix[i][j];
            }
            // bottom 向上移动
            b--;
            // 判断是否遍历完毕
            if(b<t) break;
            // 从下向上遍历
            for(int i=b,j=l;i>=t;i--){
                res[k++] = matrix[i][j];
            }
            // left 向左移动
            l++;
            // 判断是否遍历完毕
            if(l>r) break;
        }
        return res;
    }
}

包含main函数的栈

剑指 Offer 30. 包含min函数的栈 - 力扣（Leetcode）

题目要求

定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

例子：

1
2
3
4
5
6
7
8
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.min();   --> 返回 -2.

提示：

  • 各函数的调用总次数不超过 20000 次

思路分析

  • push操作：定义两个栈stack1和stack2，stack1遇到值正常入栈，遇到stack2先判断stack2是否为空或者入栈的值是否小于等于stack2栈顶元素，如果满足条件就直接入栈，否则不入栈；
  • pop操作：stack1栈顶元素与stack2栈顶元素进行比较，如果相等，那么stack2出栈，否则stack1出栈。
  • top：返回stack1的栈顶元素
  • min：返回stack2的栈顶元素

代码实现

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
class MinStack {
    // 定义两个栈
    Stack<Integer> stack1;
    Stack<Integer> stack2;
    /** initialize your data structure here. */
    public MinStack() {
        // 初始化
        stack1 = new Stack();
        stack2 = new Stack();
    }
    
    public void push(int x) {
        // 入栈
        // stack1正常进栈
        stack1.push(x);
        // stack2需要进行判断
        // 如果stack2为空或者x小于stack2栈顶元素
        // Integer 数值>127时，我们这里拿到的时对象的地址，所以需要使用.intValue()拿到真正的值
        if(stack2.isEmpty() || x<=stack2.peek().intValue()){
            stack2.push(x);
        }
    }
    
    public void pop() {
        // 出栈
        // 判断栈是否为空
        if(!stack1.isEmpty()){
            // 如果stack1栈顶元素等于stack2栈顶元素，那stack2就出栈，否则stack1出栈
            if(stack1.pop().equals(stack2.peek())){
                stack2.pop();
            }
        }
    }
    
    public int top() {
        // stack1栈顶元素
        return stack1.peek();
    }
    
    public int min() {
        // 栈中最小值
        return stack2.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.min();
 */

栈的压入、弹出序列

剑指 Offer 31. 栈的压入、弹出序列 - 力扣（Leetcode）

题目要求

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

例子：

1
2
3
4
5
6
7
8
9
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
    
输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。

提示：

  • 0 <= pushed.length == popped.length <= 1000
  • ``0 <= pushed[i], popped[i] < 1000`
  • pushed 是 popped 的排列。

思路分析

  • 根据题意，我们直到入栈和出栈的结果用两个数组保存，并且结果是确定的，那么我们应该明确入栈和出栈的步骤已经是确定了的(且唯一)。
  • 通过定义一个栈模拟入栈和出栈的操作，出栈时与popped比较是否相等，如果相等就出栈；
  • 最后判断我们定义的栈是否为空，为空说明入栈和出栈能够匹配，返回true，否则返回false；

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        // 特殊情况
        if(pushed == null || pushed.length <= 0){
            return true;
        }
        // 定义一个栈
        Stack<Integer> stack = new Stack();
        int k = 0;
        // 模拟入栈
        for(int i=0;i<pushed.length;i++){
            stack.push(pushed[i]);
            // 模拟出栈，并进行判断
            while(!stack.isEmpty() && stack.peek() == popped[k]){
                stack.pop();
                k++;
            }
        }
        // 返回结果
        return stack.isEmpty();
    }
}

从上到下打印二叉树Ⅰ

剑指 Offer 32 - I. 从上到下打印二叉树 - 力扣（Leetcode）

题目要求

从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。

例子：

1
2
3
4
5
6
7
8
9
给定二叉树: [3,9,20,null,null,15,7]
    3
   / \
  9  20
    /  \
   15   7
        
返回：
[3,9,20,15,7]

提示：

节点总数 <= 1000

思路分析

  • 对于一层层打印二叉树，一般都使用队列(先进先出)来实现；
  • 先把二叉树头节点放入队列，然后进入循环：
    • 把队列里的元素拿出来，把它的左右子树放入到队列中；
    • 然后继续把队列里的元素拿出来并用集合存放，然后把左右子树放入到队列中；
    • 如此循环，直到队列为空；
  • 将集合转换为数组返回即可；

代码实现

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] levelOrder(TreeNode root) {
        // 判断二叉树是否为空
        if(root == null){
            return new int[0];
        }
        // 定义一个队列
        Queue<TreeNode> queue = new LinkedList<>();
        // 定义一个集合，存放值
        List<Integer> res = new ArrayList<>();
        // 将树的头节点放入队列
        queue.add(root);
        // 循环
        while(!queue.isEmpty()){
            // 将队列中的元素取出,生成树
            TreeNode t = queue.poll();
            // 使用集合存放新的树的值
            res.add(t.val);
            // 将新的树的左右子树放入到队列中(前提左右子树不为空)
            if(t.left != null) queue.add(t.left);
            if(t.right != null) queue.add(t.right);
        }
        // 将集合转为数组返回即可
        int[] arr = new int[res.size()];
        for(int i=0;i< res.size();i++){
            arr[i] = res.get(i);
        }
        return arr;
    }
}