二叉树专项训练LeetCode

144. 二叉树的前序遍历

二叉树入门递归与迭代

class Solution {List<Integer> ans = new ArrayList<>();void dfs(TreeNode root){if(root == null) {return;}ans.add(root.val);dfs(root.left);dfs(root.right);}public List<Integer> preorderTraversal(TreeNode root) {dfs(root);return ans;}//迭代public List<Integer> preorderTraversal2(TreeNode root) {List<Integer> list = new ArrayList<>();if (root == null) {return list;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()) {TreeNode node = stack.pop();list.add(node.val);if (node.right != null) {stack.add(node.right);}if(node.left != null){stack.add(node.left);}}return list;}}

145. 二叉树的后序遍历

class Solution {List<Integer> ans = new ArrayList<>();void dfs(TreeNode root){if(root == null) {return;}dfs(root.left);dfs(root.right);ans.add(root.val);}public List<Integer> postorderTraversal(TreeNode root) {dfs(root);return ans;}//迭代 左右子换顺序进入栈 最后再反转list即为后序public List<Integer> postorderTraversal2(TreeNode root) {List<Integer> list = new ArrayList<>();if (root == null) {return list;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()) {TreeNode node = stack.pop();list.add(node.val);if(node.left != null){stack.add(node.left);}if (node.right != null) {stack.add(node.right);}}Collections.reverse(list);return list;}}

94. 二叉树的中序遍历

class Solution {List<Integer> ans = new ArrayList<>();void dfs(TreeNode root){if(root == null) {return;}dfs(root.left);ans.add(root.val);dfs(root.right);}public List<Integer> inorderTraversal(TreeNode root) {dfs(root);return ans;}//迭代public List<Integer> inorderTraversal2(TreeNode root) {List<Integer> list = new ArrayList<>();if (root == null) {return list;}Stack<TreeNode> stack = new Stack<>();TreeNode x = root;while (x != null || !stack.isEmpty()) {if (x != null) {stack.push(x);x = x.left;}else{x = stack.pop();list.add(x.val);x = x.right;}}return list;}//能进行统一迭代法 只需改变压栈的顺序即可实现 前中后序遍历 这里只演示中序public List<Integer> inorderTraversal3(TreeNode root) {List<Integer> list = new ArrayList<>();if (root == null) {return list;}Stack<TreeNode> stack = new Stack<>();stack.push(root);while (!stack.isEmpty()) {TreeNode now = stack.peek();if (now != null) {TreeNode x = stack.pop();if (x.right != null) {stack.add(x.right);}stack.add(x);stack.add(null);if (x.left != null) {stack.add(x.left);}} else {stack.pop();TreeNode x = stack.pop();list.add(x.val);}}return list;}}

102. 二叉树的层序遍历

class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> ans = new ArrayList<>();Queue<TreeNode> queue = new ArrayDeque<>();if(root == null){return new ArrayList<>();}queue.add(root);while (!queue.isEmpty()) {int size = queue.size();List<Integer> list = new ArrayList<>();//不能 i < queue.size  因为queue长度再不断变化 每一个for循环就是一层for (int i = 0; i < size; i++) {TreeNode now = queue.poll();list.add(now.val);if (now.left != null) {queue.add(now.left);}if (now.right != null) {queue.add(now.right);}}ans.add(list);}return ans;}}

107. 二叉树的层序遍历 II

只需要改变插入List的顺序即可头插入

class Solution {public List<List<Integer>> levelOrderBottom(TreeNode root) {List<List<Integer>> ans = new Stack<>();Queue<TreeNode> queue = new ArrayDeque<>();if(root == null){return new ArrayList<>();}queue.add(root);while (!queue.isEmpty()) {int size = queue.size();List<Integer> list = new ArrayList<>();//不能 i < queue.size  因为queue长度再不断变化 每一个for循环就是一层for (int i = 0; i < size; i++) {TreeNode now = queue.poll();list.add(now.val);if (now.left != null) {queue.add(now.left);}if (now.right != null) {queue.add(now.right);}}ans.add(0,list);}return ans;}}

199. 二叉树的右视图

class Solution {List<Integer> list = new ArrayList<>();void dfs(TreeNode x, int deep) {if (x != null) {if (deep == list.size()) {list.add(x.val);}dfs(x.right, deep + 1);dfs(x.left, deep + 1);}}public List<Integer> rightSideView(TreeNode root) {dfs(root, 0);return list;}}

637. 二叉树的层平均值

int 不够

class Solution {public List<Double> averageOfLevels(TreeNode root) {List<Double> ans = new ArrayList<>();Queue<TreeNode> queue = new ArrayDeque<>();queue.add(root);while(!queue.isEmpty()){int size = queue.size();long sum = 0;for(int i = 0 ; i < size;i++){TreeNode now = queue.poll();sum += now.val;if(now.left!=null) {queue.add(now.left);}if(now.right!=null){queue.add(now.right);}}ans.add(sum*1.0/size);}return ans;}}

429. N 叉树的层序遍历

class Solution {public List<List<Integer>> levelOrder(Node root) {List<List<Integer>> ans = new ArrayList<>();Queue<Node> queue = new ArrayDeque<>();if(root == null){return new ArrayList<>();}queue.add(root);while(!queue.isEmpty()){int size = queue.size();List<Integer> now = new ArrayList<>();for(int i = 0 ; i < size;i++){Node x = queue.poll();now.add(x.val);for(int j = 0 ; j < x.children.size();j++){queue.add(x.children.get(j));}}ans.add(now);}return ans;}}

515. 在每个树行中找最大值

class Solution {public List<Integer> largestValues(TreeNode root) {List<Integer> ans = new ArrayList<>();Queue<TreeNode> queue = new ArrayDeque<>();if (root == null) {return new ArrayList<>();}queue.add(root);while (!queue.isEmpty()) {int size = queue.size();int Max = Integer.MIN_VALUE;for (int i = 0; i < size; i++) {TreeNode now = queue.poll();Max = Math.max(Max,now.val);if (now.left != null) {queue.add(now.left);}if (now.right != null) {queue.add(now.right);}}ans.add(Max);}return ans;}}

429. N 叉树的层序遍历

class Solution {public List<List<Integer>> levelOrder(Node root) {List<List<Integer>> ans = new ArrayList<>();Queue<Node> queue = new ArrayDeque<>();if(root == null){return new ArrayList<>();}queue.add(root);while(!queue.isEmpty()){int size = queue.size();List<Integer> now = new ArrayList<>();for(int i = 0 ; i < size;i++){Node x = queue.poll();now.add(x.val);for(int j = 0 ; j < x.children.size();j++){queue.add(x.children.get(j));}}ans.add(now);}return ans;}}

104. 二叉树的最大深度

递归找

class Solution {int dep = 0;void find(TreeNode x, int deep) {if (x == null) {return;}dep = Math.max(dep, deep);find(x.left, deep + 1);find(x.right, deep + 1);}public int maxDepth(TreeNode root) {find(root,1);return dep;}}

111. 二叉树的最小深度

class Solution {int dep = Integer.MAX_VALUE;void find(TreeNode x, int deep) {if (x == null) {return;}if (x.left == null && x.right == null) {dep = Math.min(dep, deep);}find(x.left, deep + 1);find(x.right, deep + 1);}public int minDepth(TreeNode root) {if(root == null){return 0;}find(root,1);return dep;}}

226. 翻转二叉树

class Solution {public TreeNode invertTree(TreeNode root) {if (root == null) {return null;}TreeNode tmp = root.left == null ? null : root.left;root.left = root.right == null ? null : root.right;root.right = tmp;if (root.right != null) {invertTree(root.right);}if (root.left != null) {invertTree(root.left);}return root;}public TreeNode invertTree2(TreeNode root) {if (root == null) {return null;}Queue<TreeNode> queue = new ArrayDeque<>();queue.add(root);while (!queue.isEmpty()) {int size = queue.size();for (int i = 0; i < size; i++) {TreeNode now = queue.poll();TreeNode temp = now.left;now.left = now.right;now.right = temp;if (now.left != null) {queue.offer(now.left);}if (now.right != null) {queue.offer(now.right);}}}return root;}}

101. 对称二叉树

class Solution {public boolean isSymmetric(TreeNode root) {if(root==null) {return true;}return dfs(root.left,root.right);}boolean dfs(TreeNode left, TreeNode right) {if(left==null && right==null) {return true;}if(left==null || right==null) {return false;}if(left.val!=right.val) {return false;}return dfs(left.left,right.right) && dfs(left.right,right.left);}}

104. 二叉树的最大深度

class Solution {int dep = 0;void find(TreeNode x, int deep) {if (x == null) {return;}dep = Math.max(dep, deep);find(x.left, deep + 1);find(x.right, deep + 1);}public int maxDepth(TreeNode root) {find(root,1);return dep;}}

222. 完全二叉树的节点个数

class Solution {int ans = 0;void sum(TreeNode root){if(root == null) {return;}ans++;sum(root.left);sum(root.right);}public int countNodes(TreeNode root) {sum(root);return ans;}}

110. 平衡二叉树

class Solution {public boolean isBalanced(TreeNode root) {if (root == null) {return true;} else {return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);}}public int height(TreeNode root) {if (root == null) {return 0;} else {return Math.max(height(root.left), height(root.right)) + 1;}}}

257. 二叉树的所有路径

class Solution {List<Integer> path = new ArrayList<>();List<String> ans = new ArrayList<>();void search(TreeNode root) {path.add(root.val);if (root.left == null && root.right == null) {StringBuffer sb = new StringBuffer();for (int i = 0; i < path.size(); i++) {if (i != 0) {sb.append("->");}sb.append(path.get(i));}ans.add(sb.toString());return;}if(root.left != null){search(root.left);path.remove(path.size()-1);}if(root.right != null){search(root.right);path.remove(path.size()-1);}}public List<String> binaryTreePaths(TreeNode root) {if(root == null){return new ArrayList<>();}search(root);return ans;}}

404. 左叶子之和

class Solution {public int sumOfLeftLeaves(TreeNode root) {Queue<TreeNode> queue = new ArrayDeque<>();if (root == null) {return 0;}queue.offer(root);int sum = 0;while (!queue.isEmpty()) {TreeNode now = queue.poll();if (now.left != null) {if(now.left.left==null && now.left.right==null){sum+=now.left.val;}queue.add(now.left);}if(now.right!=null){queue.add(now.right);}}return sum;}}

513. 找树左下角的值

class Solution {int dep = 0;int ans = -1;void dfs(TreeNode x , int deep){if(x == null){return;}if(x.left == null && x.right == null){if(deep > dep){dep = deep;ans = x.val;}}dfs(x.left,deep+1);dfs(x.right,deep+1);}public int findBottomLeftValue(TreeNode root) {dfs(root,1);return ans;}}

112. 路径总和

class Solution {boolean ans = false;void dfs(TreeNode x, int target, int now) {if (x == null) {return;}if (x.left == null && x.right == null) {if (now+x.val == target) {ans = true;}}if (x.left != null) {dfs(x.left, target, now + x.val);}if (x.right != null) {dfs(x.right, target, now + x.val);}}public boolean hasPathSum(TreeNode root, int targetSum) {if(root == null){return false;}dfs(root, targetSum,0);return ans;}}

106. 从中序与后序遍历序列构造二叉树

class Solution {Map<Integer, Integer> map;TreeNode dfs(int[] inorder, int l1, int r1, int[] postorder, int l2, int r2) {if(l1 >= r1 || l2 >= r2){return null;}int index = map.get(postorder[r2 -1]);TreeNode root = new TreeNode(inorder[index]);int len = index - l1;root.left = dfs(inorder,l1,index,postorder,l2,l2+len);root.right= dfs(inorder,index+1,r1,postorder,l2+len,r2-1);return root;}public TreeNode buildTree(int[] inorder, int[] postorder) {map = new HashMap<>();for (int i = 0; i < inorder.length; i++) {map.put(inorder[i], i);}return dfs(inorder, 0, inorder.length, postorder, 0, postorder.length);}}

105. 从前序与中序遍历序列构造二叉树

class Solution {Map<Integer, Integer> map;TreeNode dfs(int[] preorder, int l1, int r1, int[] inorder, int l2, int r2) {if(l1 >= r1 || l2 >= r2){return null;}int index = map.get(preorder[l1]);TreeNode root = new TreeNode(inorder[index]);int len = index - l2;root.left = dfs(preorder,l1+1,l1+len+1,inorder,l2,index);root.right= dfs(preorder,l1+len+1,r1,inorder,index+1,r2);return root;}public TreeNode buildTree(int[] preorder, int[] inorder) {map = new HashMap<>();for (int i = 0; i < inorder.length; i++) {map.put(inorder[i], i);}return dfs(preorder, 0, preorder.length, inorder, 0, inorder.length);}}

654. 最大二叉树

class Solution {TreeNode dfs(int[] nums, int l, int r) {if (l >= r) {return null;}int MAX = -1;int index = -1;for (int i = l; i < r; i++) {if (nums[i] > MAX) {MAX = nums[i];index = i;}}TreeNode root = new TreeNode(MAX);root.left = dfs(nums, l, index);root.right = dfs(nums, index + 1, r);return root;}public TreeNode constructMaximumBinaryTree(int[] nums) {TreeNode root = dfs(nums, 0, nums.length);return root;}}

617. 合并二叉树

class Solution {public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if (root1 == null) {return root2;}if (root2 == null) {return root1;}root1.val += root2.val;root1.left = mergeTrees(root1.left,root2.left);root1.right = mergeTrees(root1.right,root2.right);return root1;}}

700. 二叉搜索树中的搜索

class Solution {public TreeNode searchBST(TreeNode root, int val) {if(root == null){return null;}if(root.val == val){return root;}if(val < root.val){return searchBST(root.left,val);}else{return searchBST(root.right,val);}}}

8. 验证二叉搜索树

class Solution {boolean ans = true;public void f(TreeNode root, long lower, long upper) {if (root.val <= lower || root.val >= upper) {ans = false;}if (root.left != null) {f(root.left, lower, root.val);}if (root.right != null) {f(root.right, root.val, upper);}}public boolean isValidBST(TreeNode root) {f(root, Long.MIN_VALUE, Long.MAX_VALUE);if (ans) {return true;} else {return false;}}}