hot100 |八、二叉树

1-leetcode94. 二叉树的中序遍历

注意：√

1. 递归方法已经很熟练了，两种不同的递归方式
2. 迭代法需要注意，zrm就遇到了要求迭代实现，前序遍历和后续遍历其实不难，中序遍历用的少，注意看一看

// 1.递归方法1List<Integer> res = new ArrayList<>();public List<Integer> inorderTraversal(TreeNode root) {traverse(root);return res;}private void traverse(TreeNode root) {if (root == null) {return;}traverse(root.left);// 中序位置res.add(root.val);traverse(root.right);}// 2.递归方法2public List<Integer> inorderTraversal1(TreeNode root) {List<Integer> res = new ArrayList<>();if (root == null) {return res;}res.addAll(inorderTraversal1(root.left));res.add(root.val);res.addAll(inorderTraversal1(root.right));return res;}// 3.迭代方法public List<Integer> inorderTraversal2(TreeNode root) {List<Integer> res = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();TreeNode cur = root;while (cur != null || !stack.isEmpty()) {if (cur != null) {stack.add(cur);cur = cur.left;}else {cur = stack.pop();res.add(cur.val);cur = cur.right;}}return res;}

2-leetcode104. 二叉树的最大深度

注意：√

1. 动态规划思想，秒杀

    public int maxDepth(TreeNode root) {if (root == null){return 0;}int leftDepth = maxDepth(root.left);int rightDepth = maxDepth(root.right);return Math.max(leftDepth, rightDepth) +1;}

3-leetcode226. 翻转二叉树

注意：√

1. 递归的思想，注意一下要提前保存左右的节点索引

    public TreeNode invertTree(TreeNode root) {if (root == null){return null;}TreeNode leftNode = root.left;TreeNode rightNode = root.right;root.left = invertTree(rightNode);root.right = invertTree(leftNode);return root;}

4-leetcode101. 对称二叉树

注意：×

1. 建议直接使用队列的方式，不过注意加入队列的方式，很巧妙 左左，右右， 左右， 右左

    public boolean isSymmetric(TreeNode root) {LinkedList<TreeNode> queue = new LinkedList<>();queue.add(root.left);queue.add(root.right);while (queue.size()>0){TreeNode le = queue.pollFirst();TreeNode ri = queue.pollFirst();if (le == null && ri == null){continue;}if (le == null || ri == null){return false;}if (le.val != ri.val) {return false;}queue.add(le.left);queue.add(ri.right);queue.add(le.right);queue.add(ri.left);}return true;}

5-leetcode543. 二叉树的直径

注意：×

1. 学习Labuladong，这题可以由maxDepth转过来
2. 注意的地方是，这个题目要的是二叉树的直径，也就是路径值，路径值和深度需要体会一下
3. 直径长就是左右两个深度加起来

    int res = 0;public int diameterOfBinaryTree(TreeNode root) {int x = maxDepth(root);return res;}public int maxDepth(TreeNode root) {if (root == null){return 0;}int leftDepth = maxDepth(root.left);int rightDepth = maxDepth(root.right);int curDepth = leftDepth + rightDepth;res = Math.max(curDepth, res);return Math.max(leftDepth, rightDepth) +1;}

6-leetcode102. 二叉树的层序遍历

注意：××

1. 注意加入queue的时候，要判断是不是空
2. while循环判断是不是空，不要用size会浪费时间
3. 最开始就给res = new LinkedList这样判断root == null的时候可以直接返回结果

    public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> res = new LinkedList<>();if (root == null){return res;}LinkedList<TreeNode> queue = new LinkedList<>();queue.add(root);// while (queue.size()>0){while (! queue.isEmpty()){int num = queue.size();List<Integer> list = new LinkedList<>();for (int i = 0; i < num; i++) {TreeNode node = queue.poll();list.add(node.val);if (node.left != null){queue.add(node.left);}if (node.right != null){queue.add(node.right);}}res.add(list);}return res;}

leetcode

注意：√×