[刷题记录Day15]Leetcode二叉树

番茄随想 / 2023-08-26 / 原文

No.1

题目

二叉树的层序遍历

思路

使用队列
关键点：1. 每进入一层，层内的节点都被处理完成 2. 开始遍历层内的节点前，必须先记录该层的节点数量，不能访问到下一层的节点

代码

public List<List<Integer>> levelOrder(TreeNode root) {  
    Queue<TreeNode> queue = new LinkedList<>();  
    queue.add(root);  
    List<List<Integer>> result = new ArrayList<>();  
  
    if (root == null)  
        return result;  
  
    // 外循环，遍历每一层  
    while (queue.size() > 0) {  
        List<Integer> list = new ArrayList<>();  
        // 内循环，遍历每一层的节点  
        int levelNum = queue.size();  
        for (int i = 0; i < levelNum; i++) {  
            TreeNode cur = queue.poll();  
            list.add(cur.val);  
            if (cur.left != null)  
                queue.add(cur.left);  
            if (cur.right != null)  
                queue.add(cur.right);  
        }  
        result.add(list);  
    }  
  
    return result;  
}

No.2

题目

翻转二叉树

思路

递归
这道题目使用前序遍历和后序遍历都可以，唯独中序遍历不方便，因为中序遍历会把某些节点的左右孩子翻转了两次！建议拿纸画一画，就理解了

代码

public void invert(TreeNode node) {  
    if (node == null)  
        return;  
  
    invert(node.left);  
    invert(node.right);  
  
    TreeNode temp = node.left;  
    node.left = node.right;  
    node.right = temp;  
}  
  
public TreeNode invertTree(TreeNode root) {  
    invert(root);  
  
    return root;  
}

No.3

题目

对称二叉树

非递归思路

非递归写法，用队列
每一层，左右指针向中间靠拢，检查对称性
利用越界数据表示异常

非递归代码

public boolean isSymmetric(TreeNode root) {  
    Queue<TreeNode> queue = new LinkedList<>();  
    queue.add(root);  
  
    // 遍历层  
    while (queue.size() > 0) {  
        int nodeNum = queue.size();  
  
        if (queue.peek() != root && queue.size() % 2 != 0)  
            return false;  
  
        // 存储这一层的节点  
        int[] level = new int[nodeNum];  
        // 遍历每一层的节点  
        for (int i = 0; i < nodeNum; i++) {  
            TreeNode cur = queue.poll();  
            if (cur != null) {  
                level[i] = cur.val;  
                queue.add(cur.left);  
                queue.add(cur.right);  
            } else  
                level[i] = 101; // 用越界数据表示异常，-100 <= Node.val <= 100  
        }  
  
        int left = 0, right = nodeNum - 1;  
        while (left < right) {  
            if (level[left] != level[right])  
                return false;  
            left++;  
            right--;  
        }  
    }  
  
    return true;  
}