• 欢迎光临~

代码随想录训练营|Day 15|102, 226, 101

开发技术 开发技术 2022-10-04 次浏览

102. Binary Tree Level Order Traversal

Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

Example 1:

代码随想录训练营|Day 15|102, 226, 101

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

Example 2:

Input: root = [1]
Output: [[1]]

Example 3:

Input: root = []
Output: []

Constraints:

  • The number of nodes in the tree is in the range [0, 2000].
  • 1000 <= Node.val <= 1000

学会二叉树的层序遍历,可以一口气打完以下十题:

102.二叉树的层序遍历
107.二叉树的层次遍历II
199.二叉树的右视图
637.二叉树的层平均值
429.N叉树的层序遍历
515.在每个树行中找最大值
116.填充每个节点的下一个右侧节点指针
117.填充每个节点的下一个右侧节点指针II
104.二叉树的最大深度
111.二叉树的最小深度

逐层地,从左到右访问所有节点

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null) return ans;
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int qlen = queue.size();
            List<Integer> row = new ArrayList<>();
            for (int i = 0; i < qlen; i++) {
                TreeNode curr = queue.poll();
                row.add(curr.val);
                if (curr.left != null) queue.add(curr.left);
                if (curr.right != null) queue.add(curr.right);
            }
            ans.add(row);
        }
        return ans;
    }
}

Time Complexity:O(n)
Space Complexity:O(n)

For Future References

题目链接:https://leetcode.com/problems/binary-tree-level-order-traversal/

文章讲解:https://programmercarl.com/0102.二叉树的层序遍历.html

视频讲解:https://www.bilibili.com/video/BV1GY4y1u7b2/


226. Invert Binary Tree

Given the root of a binary tree, invert the tree, and return its root.

Example 1:

代码随想录训练营|Day 15|102, 226, 101

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Example 2:

代码随想录训练营|Day 15|102, 226, 101

Input: root = [2,1,3]
Output: [2,3,1]

Example 3:

Input: root = []
Output: []

Constraints:

  • The number of nodes in the tree is in the range [0, 100].
  • 100 <= Node.val <= 100

这道题目使用前序遍历和后序遍历都可以,唯独中序遍历不方便,因为中序遍历会把某些节点的左右孩子翻转了两次

DFS

class Solution {
   /**
     * 前后序遍历都可以
     * 中序不行,因为先左孩子交换孩子,再根交换孩子(做完后,右孩子已经变成了原来的左孩子),再右孩子交换孩子(此时其实是对原来的左孩子做交换)
     */
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        invertTree(root.left);
        invertTree(root.right);
        swapChildren(root);
        return root;
    }

    private void swapChildren(TreeNode root) {
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
    }
}

BFS

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {return null;}
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        deque.offer(root);
        while (!deque.isEmpty()) {
            int size = deque.size();
            while (size-- > 0) {
                TreeNode node = deque.poll();
                swap(node);
                if (node.left != null) {deque.offer(node.left);}
                if (node.right != null) {deque.offer(node.right);}
            }
        }
        return root;
    }

    public void swap(TreeNode root) {
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }
}

Time Complexity:O(n)
Space Complexity:O(n)

For Future References

题目链接:https://leetcode.com/problems/invert-binary-tree/

文章讲解:https://programmercarl.com/0226.翻转二叉树.html

视频讲解:https://www.bilibili.com/video/BV1sP4y1f7q7/


101. Symmetric Tree

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Example 1:

代码随想录训练营|Day 15|102, 226, 101

Input: root = [1,2,2,3,4,4,3]
Output: true

Example 2:

代码随想录训练营|Day 15|102, 226, 101

Input: root = [1,2,2,null,3,null,3]
Output: false

Constraints:

  • The number of nodes in the tree is in the range [1, 1000].
  • 100 <= Node.val <= 100

Follow up:

Could you solve it both recursively and iteratively?

对于二叉树是否对称,要比较的是根节点的左子树与右子树是不是相互翻转的,理解这一点就知道了其实我们要比较的是两个树(这两个树是根节点的左右子树)

节点为空的情况有:(注意我们比较的其实不是左孩子和右孩子,所以如下我称之为左节点右节点)

  • 左节点为空,右节点不为空,不对称,return false
  • 左不为空,右为空,不对称 return false
  • 左右都为空,对称,返回true

此时已经排除掉了节点为空的情况,那么剩下的就是左右节点不为空:

  • 左右都不为空,比较节点数值,不相同就return false

比较二叉树外侧是否对称:传入的是左节点的左孩子,右节点的右孩子。
比较内测是否对称,传入左节点的右孩子,右节点的左孩子。
如果左右都对称就返回true ,有一侧不对称就返回false 。

public boolean isSymmetric1(TreeNode root) {
        return compare(root.left, root.right);
}

private boolean compare(TreeNode left, TreeNode right) {

     if (left == null && right != null) {
            return false;
     }
     if (left != null && right == null) {
            return false;
     }

     if (left == null && right == null) {
            return true;
     }
     if (left.val != right.val) {
            return false;
     }
     // 比较外侧
     boolean compareOutside = compare(left.left, right.right);
     // 比较内侧
     boolean compareInside = compare(left.right, right.left);
     return compareOutside && compareInside;
}

Time Complexity:O(n)
Space Complexity:O(n)

For Future References

题目链接:https://leetcode.com/problems/symmetric-tree/

文章讲解:https://programmercarl.com/0101.对称二叉树.html#递归法

视频讲解:https://www.bilibili.com/video/BV1ue4y1Y7Mf/

程序员灯塔
转载请注明原文链接:代码随想录训练营|Day 15|102, 226, 101
喜欢 (0)