526互联

day2

发布时间 2023-03-28 11:45:20作者: 黄三七

1、层序遍历（广度优先遍历）

  • 借助 队列 实现

    • 队列 先进先出，符合一层一层遍历的逻辑
    • 栈 先进后出，适合模拟深度优先遍历（递归）

  • leetcode102 二叉树的层序遍历

    1. 迭代法（使用队列）【模板题】

      class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        Deque<TreeNode> queue = new ArrayDeque<>();
        if(root != null) {
            queue.offerLast(root);
        }
        while(!queue.isEmpty()) {
            List<Integer> layRes = new ArrayList<>();
            int size = queue.size();
            for(int i=0; i<size; i++) {
                TreeNode node = queue.pollFirst();
                layRes.add(node.val);
                if(node.left!=null) {
                    queue.offerLast(node.left);
                }
                if(node.right!=null) {
                    queue.offerLast(node.right);
                }
            }
            res.add(layRes);
        }
        return res;
    }
}

    2. 递归法

      class Solution {
    List<List<Integer>> res = new ArrayList<List<Integer>>();

    public List<List<Integer>> levelOrder(TreeNode root) {
        backTracking(root,0);
        return res;
    }

    public void backTracking(TreeNode node, int depth) {
        if(node == null) {
            return;
        }
        if(res.size() == depth) {
            res.add(new ArrayList<Integer>());
        }

        res.get(depth).add(node.val);
        backTracking(node.left, depth+1);
        backTracking(node.right, depth+1);
    }

}

2、leetcode226 翻转二叉树

  1. 思路：交换每个节点的左右孩子节点 ===> 需要去遍历每个节点

  2. 遍历顺序：前序遍历、后序遍历、层序遍历

    • 中序遍历不方便，因为中序遍历会把某些节点的左右孩子翻转两次

  3. 代码

    class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null) {
            return null;
        }
        swap(root);
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

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

3、leetcode101 对称二叉树

  1. 思路：

    • 判断二叉树是否镜像对称 ===> 根节点的左右子树是否可相互翻转 ===> 需比较根节点的左右子树 ===> 需要遍历两棵树 ===>比较两棵子树的里侧、外层元素是否对应相等
    • 遍历顺序：
      • 需要从下往上 and 比较的是两棵子树的里侧、外侧
      • 一棵：左右中
      • 另一棵：右左中

  2. 递归法

    1. 确定递归函数的参数和返回值

      • 比较的是根节点的两个子树是否是相互翻转的，进而判断这个树是不是对称树，所以要比较的是两个树，参数自然也是左子树节点和右子树节点。

    2. 确定终止条件

      • 先处理空节点问题、以及左右节点不为空但不相等的情况

    3. 确定单层递归的逻辑

      • 处理 左右节点都不为空，且数值相同的情况。
      • 比较二叉树外侧是否对称
      • 比较内侧是否对称
      • 如果左右都对称就返回true ，有一侧不对称就返回false

    4. 代码

      class Solution {
    public boolean isSymmetric(TreeNode root) {
        return compare(root.left, root.right);
    }

    public boolean compare(TreeNode left, TreeNode right) {
        if(left == null && right == null) {
            return true;
        } else if(left == null && right != null) {
            return false;
        } else if(left != null && right == null) {
            return false;
        } else if(left.val != right.val) {
            return false;
        }

        boolean outside = compare(left.left, right.right);
        boolean inside = compare(left.right, right.left);
        return outside&&inside;
    }
}