leetcode104 二叉树的最大深度

给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 

  1. leetcode 104
  2. //DFS 深度优先 v1.0    
  3. class Solution {
  4.     public int maxDepth(TreeNode root) {
  5.         if(root == null) return 0;
  6.         int leftDepth = maxDepth(root.left);
  7.         int rightDepth = maxDepth(root.right);
  8.         return Math.max(leftDepth,rightDepth)+1;
  9.     }
  10. }
  11. //v2.0
  12. class Solution {
  13.     public int maxDepth(TreeNode root) {
  14.      return root == null?0:Math.max(maxDepth(root.left),maxDepth(root.right))+1;
  15.     }
  16. }
  18. //BFS 广度优先
  19. class Solution {
  20.     public int maxDepth(TreeNode root) {
  21.         if(root==null) return 0;
  22.         int depth = 0;
  23.         Queue<TreeNode> tree = new LinkedList<TreeNode>();
  24.         tree.offer(root);
  25.         while(!tree.isEmpty()){
  26.             int size = tree.size();           
  27.             while(size>0){
  28.                 TreeNode node = tree.poll();
  29.                 if(node.left!=null) tree.offer(node.left);
  30.                 if(node.right!=null) tree.offer(node.right);
  31.                 size--;
  32.             }
  33.             depth++;            
  34.         }
  35.         return depth;
  36.     }
  37. }

leetcode94 二叉树的中序遍历

  1.  //v1.0 递归
  2. class Solution {
  3.     List<Integer> list = new ArrayList<>();
  4.     public List<Integer> inorderTraversal(TreeNode root) {
  5.         if(root==null) return list;      
  6.         inorderTraversal(root.left);
  7.         list.add(root.val);
  8.         inorderTraversal(root.right);
  9.         return list;
  10.     }
  11. }
  12. //v2.0 迭代
  13. class Solution {
  15.     public List<Integer> inorderTraversal(TreeNode root) {
  16.         List<Integer> list = new ArrayList<>();
  17.         Stack<TreeNode> stack = new Stack<>();
  18.         if(root==null) return list;
  19.         TreeNode curr = root;
  20.         while(curr!=null||!stack.isEmpty()){
  21.             if(curr!=null){
  22.                 stack.push(curr);
  23.                 curr = curr.left;
  24.             }else{
  25.                 curr = stack.pop();
  26.                 list.add(curr.val);
  27.                 curr = curr.right;
  28.             }
  29.         }
  30.         return list;
  31.     }
  32. }

leetcode102 二叉树的层序遍历

  1. class Solution {
  2.     public List<List<Integer>> levelOrder(TreeNode root) {
  3.         if(root==null) return new ArrayList<>();
  4.         List<List<Integer>> res = new ArrayList<>();
  5.         Queue<TreeNode> que = new LinkedList<>();
  6.         que.offer(root);
  8.         while(!que.isEmpty()){
  9.             int size = que.size();
  10.             List<Integer> list = new ArrayList<>();
  11.             while(size>0){
  12.                 TreeNode node = que.poll();
  13.                 list.add(node.val);
  14.                 if(node.left!=null) que.offer(node.left);
  15.                 if(node.right!=null) que.offer(node.right);
  16.                 size--;
  17.             }
  18.             res.add(list);
  19.         }
  20.         return res;
  21.     }
  22. }

leetcode207 二叉树的层序遍历 II

给定一个二叉树，返回其节点值自底向上的层序遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历） 

  1. class Solution {
  2.     public List<List<Integer>> levelOrderBottom(TreeNode root) {
  3.         List<List<Integer>> lists = new ArrayList<>();
  4.         if(root==null) return lists;
  5.         Queue<TreeNode> queue = new LinkedList<>();
  6.         queue.add(root);
  7.         while(!queue.isEmpty()){
  8.             int size = queue.size();
  9.             List<Integer> list = new ArrayList<>();
  10.             for(int i =0;i<size;i++){
  11.                 TreeNode node=queue.poll();
  12.                 if(node.left!=null) queue.add(node.left);
  13.                 if(node.right!=null) queue.add(node.right);
  14.                 list.add(node.val);
  15.             }
  16.             lists.add(list);
  17.         }
  18.         Collections.reverse(lists);
  19.         return lists;
  20.     }
  21. }

二叉树的锯齿形层序遍历

给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。 

  1. class Solution {
  2.     public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
  3.         List<List<Integer>> res = new ArrayList<>();
  4.         if(root==null) return res;
  5.         Queue<TreeNode> queue = new LinkedList<>();
  6.         queue.offer(root);
  7.         int depth=0;//树的深度
  8.         while(!queue.isEmpty()){
  9.             depth++;
  10.             int size = queue.size();
  11.             List<Integer> list = new ArrayList<>();
  12.             for(int i=0;i<size;i++){
  13.                 TreeNode node = queue.poll();
  14.                 if(node.left!=null) queue.offer(node.left);
  15.                 if(node.right!=null) queue.offer(node.right);
  16.                 list.add(node.val);
  17.             }
  18.             if(depth%2==0){
  19.                 Collections.reverse(list);
  20.             }
  21.             res.add(list);
  22.         }
  23.         return res;
  24.     }
  25. }

二叉树的右视图

  1. class Solution {
  2.     public List<Integer> rightSideView(TreeNode root) {
  3.         List<Integer> res = new ArrayList<>();
  4.         if(root==null) return res;
  5.         Queue<TreeNode> queue = new LinkedList<>();
  6.         queue.offer(root);
  7.         while(!queue.isEmpty()){
  8.             int size = queue.size();
  9.             for(int i=0;i<size;i++){
  10.                 TreeNode node = queue.poll();
  11.                 if(node.left!=null) queue.offer(node.left);
  12.                 if(node.right!=null) queue.offer(node.right);
  13.                 if(i==size-1) res.add(node.val);
  14.             }
  15.         }
  16.         return res;
  17.     }
  18. }

leetcode515 在每个树行中找最大值

  1. class Solution {
  2.     public List<Integer> largestValues(TreeNode root) {
  3.         List<Integer> res = new ArrayList<>();
  4.         if(root==null) return res;
  5.         Queue<TreeNode> queue = new LinkedList<>();
  6.         queue.offer(root);
  7.         while(!queue.isEmpty()){
  8.             int size = queue.size();
  9.             int maxValue=Integer.MIN_VALUE;
  10.             for(int i=0;i<size;i++){
  11.                 TreeNode node = queue.poll();
  12.                 if(node.left!=null) queue.offer(node.left);
  13.                 if(node.right!=null) queue.offer(node.right);
  14.                 //maxValue = Math.max(maxValue,node.val);
  15.                 if(node.val>maxValue) maxValue=node.val;
  16.             }
  17.             res.add(maxValue);
  18.         }
  19.         return res;
  20.     }
  21. }

leetcode 二叉树的层平均值

  1. class Solution {
  2.     public List<Double> averageOfLevels(TreeNode root) {
  3.         List<Double> res = new ArrayList<>();
  4.         if(root==null) return res;
  5.         Queue<TreeNode> queue = new LinkedList<>();
  6.         queue.offer(root);
  7.         while(!queue.isEmpty()){
  8.             int size = queue.size();
  9.             Double sum = 0.0;
  10.             for(int i=0;i<size;i++){
  11.                 TreeNode node = queue.poll();
  12.                 if(node.left!=null) queue.offer(node.left);
  13.                 if(node.right!=null) queue.offer(node.right);
  14.                 sum+=node.val;
  15.             }
  16.             res.add(sum/size);
  17.         }
  18.         return res;
  19.     }
  20. }

leetcode116 填充每个节点的下一个右侧节点指针

给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
初始状态下，所有 next 指针都被设置为 NULL。 

  2. class Solution {
  3.     public Node connect(Node root) {
  4.         if(root==null) return root;
  5.         if(root.left!=null){
  6.             root.left.next = root.right;
  7.             if(root.next!=null&&root.right!=null){
  8.                 root.right.next = root.next.left;
  9.             }
  10.             connect(root.left);
  11.             connect(root.right);
  12.         }
  13.         return root;
  14.     }
  15. }

leetcode98 验证二叉搜索树

  1. //v1.0 利用中序遍历，判断是否为递增，但效率较低
  2. class Solution {
  3.     private List<Integer> list = new ArrayList<>();
  4.     public boolean isValidBST(TreeNode root) {
  5.         //中序遍历为升序的二叉树为二叉搜索树
  6.         list = inorderTraversal(root);
  7.         for(int i=1;i<list.size();i++){
  8.             if(list.get(i)>list.get(i-1)){
  9.                 continue;
  10.             }else{
  11.                 return false;
  12.             }
  13.         }
  14.         return true;
  15.     }
  17.     public List<Integer> inorderTraversal(TreeNode root){
  18.         if(root==null){
  19.             return list;
  20.         }
  21.         inorderTraversal(root.left);
  22.         list.add(root.val);
  23.         inorderTraversal(root.right);
  24.         return list;
  25.     }
  26. }
  27. //v2.0
  28. class Solution {
  29.     public boolean isValidBST(TreeNode root) {
  30.         return valid(root,Long.MIN_VALUE, Long.MAX_VALUE);
  31.     }
  32.     public boolean valid(TreeNode node, long min, long max){
  33.         if(node==null){
  34.             return true;
  35.         }
  36.         if(node.val<=min||node.val>=max){
  37.             return false;
  38.         }
  39.         return valid(node.left,min,node.val)&&valid(node.right,node.val,max);
  40.     }
  41. }

leetcode114 二叉树展开为链表

https://leetcode-cn.com/problems/flatten-binary-tree-to-linked-list/solution/114-er-cha-shu-zhan-kai-wei-lian-biao-by-ming-zhi-/ ✔

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     public void flatten(TreeNode root) {
  18.         if(root==null){
  19.             return;
  20.         }
  21.         flatten(root.left); //将root的左节点转为链表
  22.         flatten(root.right); //将root的右节点转为链表
  23.         TreeNode tmp =  root.right;
  24.         root.right = root.left;
  25.         root.left = null; //将root左节点置空
  26.         while(root.right!=null){
  27.             root = root.right;
  28.         }
  29.         root.right = tmp;
  31.     }
  33. }

leetcode124 二叉树中的最大路径和

  1. class Solution {
  2.     int max = Integer.MIN_VALUE;
  3.     public int maxPathSum(TreeNode root) {
  4.         if(root==null){
  5.             return 0;
  6.         }
  7.         dfs(root);
  8.         return Math.max;
  10.     }
  11.     public int dfs(TreeNode root){
  12.         if(root==null){
  13.             return 0;
  14.         }
  15.         // 根节点左侧最大值
  16.         int leftMax = Math.max(dfs(root.left),0);
  17.         // 根节点右侧最大值
  18.         int rightMax = Math.max(dfs(root.right),0);
  19.         // 更新最大值
  20.         max = Math.max(max, leftMax+rightMax+root.val);
  21.         return Math.max(0,root.val+Math.max(leftMax,rightMax));
  22.     }
  23. }

leetcode 208 实现Trie(前缀树)

  1. class Trie {
  2.     // 子节点
  3.     Trie[] children;
  4.     // 是否为终点
  5.     boolean isEnd;
  6.     /** Initialize your data structure here. */
  7.     public Trie() {
  8.         children = new Trie[26];
  9.         isEnd = false;
  10.     }
  12.     /** Inserts a word into the trie. */
  13.     public void insert(String word) {
  14.         Trie node = this;
  16.         for(int i=0;i<word.length();i++){
  17.             int index = word.charAt(i)-'a';
  18.             if(node.children[index]==null){
  19.                 node.children[index] = new Trie();
  20.             }
  21.             node = node.children[index];
  22.         }
  23.         node.isEnd = true;
  24.     }
  26.     /** Returns if the word is in the trie. */
  27.     public boolean search(String word) {
  28.         Trie node = searchPrefix(word);
  29.         return node!=null&&node.isEnd;
  30.     }
  32.     /** Returns if there is any word in the trie that starts with the given prefix. */
  33.     public boolean startsWith(String prefix) {
  34.         return searchPrefix(prefix)!=null;
  35.     }
  37.     public Trie searchPrefix(String word){
  38.         Trie node = this;
  39.         for(int i=0;i<word.length();i++){
  40.             int index = word.charAt(i)-'a';
  41.             if(node.children[index]==null){
  42.                 return null;
  43.             }
  44.             node = node.children[index];
  45.         }
  46.         return node;
  47.     }
  48. }
  50. /**
  51.  * Your Trie object will be instantiated and called as such:
  52.  * Trie obj = new Trie();
  53.  * obj.insert(word);
  54.  * boolean param_2 = obj.search(word);
  55.  * boolean param_3 = obj.startsWith(prefix);
  56.  */

leetcode 236 二叉树的最近公共祖先

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. class Solution {
  11.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  12.         if(root == null || p==root || q==root){
  13.             return root;
  14.         }
  15.         // 在左子树中找公共祖先
  16.         TreeNode left = lowestCommonAncestor(root.left,p,q);
  17.         // 在右子树中找公共祖先
  18.         TreeNode right = lowestCommonAncestor(root.right,p,q);
  19.         if(left==null&&right==null) return null;
  20.         if(left==null) return right;
  21.         if(right==null) return left;
  22.         return root;
  23.     }
  24. }

leetcode 437 路径总和 III

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     int res = 0;
  18.     public int pathSum(TreeNode root, int targetSum) {
  19.         if(root==null){
  20.             return 0;
  21.         }
  22.         sum(root, targetSum);
  23.         pathSum(root.left, targetSum);
  24.         pathSum(root.right, targetSum);
  25.         return res;
  26.     }
  28.     public void sum(TreeNode root, int targetSum){
  29.         if(root==null) return;
  30.         targetSum -= root.val;
  31.         if(targetSum==0) res++;
  32.         sum(root.left, targetSum);
  33.         sum(root.right, targetSum);
  35.     }
  36. }

leetcode 538 把二叉搜索树转换为累加树

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode() {}
  8.  *     TreeNode(int val) { this.val = val; }
  9.  *     TreeNode(int val, TreeNode left, TreeNode right) {
  10.  *         this.val = val;
  11.  *         this.left = left;
  12.  *         this.right = right;
  13.  *     }
  14.  * }
  15.  */
  16. class Solution {
  17.     int num;
  18.     public TreeNode convertBST(TreeNode root) {
  19.         if(root==null) return null;
  20.         convertBST(root.right);
  21.         root.val = root.val + num;
  22.         num = root.val;
  23.         convertBST(root.left);
  24.         return root;
  25.     }
  26. }

剑指07 重建二叉树

  1. class Solution {
  2.     private int[] preorder;
  3.     private Map<Integer,Integer> map = new HashMap<>();
  4.     public TreeNode buildTree(int[] preorder, int[] inorder) {
  5.         //存储前序遍历
  6.         this.preorder = preorder;
  8.         for(int i=0;i<inorder.length;i++){
  9.             map.put(inorder[i],i);//存储中序遍历，方便查找根节点
  11.         }
  12.         return recur(0,0,inorder.length-1);
  14.     }
  15.     private TreeNode recur(int preRootIndex,int inLeftIndex,int inRightIndex){
  16.         if(inLeftIndex>inRightIndex) return null;
  17.         TreeNode root = new TreeNode(preorder[preRootIndex]);//根节点在前序遍历中找
  18.         int index = map.get(root.val);//找到根节点在中序遍历中的位置
  19.         root.left = recur(preRootIndex+1,inLeftIndex,index-1);
  20.         root.right = recur(preRootIndex+(index-inLeftIndex)+1,index+1,inRightIndex);
  21.         return root;
  22.     }
  23. }