二叉树 二叉树的最大深度 原题链接:https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/?envType=study-plan-v2&envId=top-interview-150
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { public int maxDepth (TreeNode root) { if (root == null ){ return 0 ; } return Math.max(maxDepth(root.left),maxDepth(root.right)) + 1 ; } }
相同的树 原题链接:https://leetcode.cn/problems/same-tree/description/?envType=study-plan-v2&envId=top-interview-150
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 class Solution { public boolean isSameTree (TreeNode p, TreeNode q) { if (p == null && q == null ){ return true ; } if (p == null || q == null ){ return false ; } if (p.val != q.val){ return false ; } return isSameTree(p.left,q.left) && isSameTree(p.right,q.right); } }
翻转二叉树 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class Solution { public TreeNode invertTree (TreeNode root) { return dfs(root); } private TreeNode dfs (TreeNode node) { if (node == null ){ return null ; } TreeNode left = dfs(node.left); TreeNode right = dfs(node.right); node.left = right; node.right = left; return node; } }
对称二叉树 原题链接:https://leetcode.cn/problems/symmetric-tree/?envType=study-plan-v2&envId=top-interview-150
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 class Solution { private 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); } public boolean isSymmetric (TreeNode root) { if (root == null ){ return true ; } return dfs(root.left,root.right); } }
从前序与中序遍历序列构造二叉树 原题链接:https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/description/?envType=study-plan-v2&envId=top-interview-150
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 class Solution { public TreeNode buildTree (int [] preorder, int [] inorder) { if (preorder.length == 0 || inorder.length == 0 ){ return null ; } TreeNode root = new TreeNode (preorder[0 ]); for (int mid = 0 ; mid< inorder.length ; mid++){ if (root.val == inorder[mid]){ int [] pre_left = Arrays.copyOfRange(preorder,1 ,mid + 1 ); int [] pre_right = Arrays.copyOfRange(preorder,mid + 1 , preorder.length); int [] in_left = Arrays.copyOfRange(inorder,0 ,mid); int [] in_right = Arrays.copyOfRange(inorder,mid + 1 ,inorder.length); root.left = buildTree(pre_left,in_left); root.right = buildTree(pre_right,in_right); break ; } } return root; } }
写法2: 用hash存储 中序树中的节点关系 这样会更好一些 也会更快一些
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 class Solution { HashMap<Integer,Integer> hash = new HashMap <>(); private int [] preorder; public TreeNode buildTree (int [] preorder, int [] inorder) { this .preorder = preorder; for (int i = 0 ; i < inorder.length ; i++){ hash.put(inorder[i],i); } return dfs(0 ,0 ,preorder.length - 1 ); } private TreeNode dfs (int root,int left,int right) { if (left > right){ return null ; } int val = preorder[root]; TreeNode node = new TreeNode (val); int mid = hash.get(val); node.left = dfs(root + 1 ,left,mid - 1 ); node.right = dfs(root + mid - left + 1 ,mid + 1 ,right); return node; } }
从中序与后序遍历序列构造二叉树 原题链接:https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/description/?envType=study-plan-v2&envId=top-interview-150
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 class Solution { int [] postorder; HashMap<Integer,Integer> hash = new HashMap <>(); public TreeNode buildTree (int [] inorder, int [] postorder) { this .postorder = postorder; for (int i = 0 ; i < inorder.length ; i++){ hash.put(inorder[i],i); } return dfs(inorder.length - 1 ,0 ,inorder.length - 1 ); } private TreeNode dfs (int root,int left,int right) { if (left > right){ return null ; } int val = postorder[root]; TreeNode node = new TreeNode (val); int mid = hash.get(val); node.right = dfs(root - 1 ,mid + 1 ,right); node.left = dfs(root - (right - mid) - 1 ,left,mid - 1 ); return node; } }
填充每个节点的下一个右侧节点指针 II 原题链接:https://leetcode.cn/problems/populating-next-right-pointers-in-each-node-ii/description/?envType=study-plan-v2&envId=top-interview-150
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 class Solution { Queue<Node>q = new LinkedList <>(); public Node connect (Node root) { if (root == null ){ return root; } q.offer(root); while (!q.isEmpty()){ int cur = q.size(); ArrayList<Node> tmp = new ArrayList <>(q); for (int i = 0 ; i < cur ; i++){ Node t = q.poll(); if (t.left != null ){ q.offer(t.left); } if (t.right != null ){ q.offer(t.right); } if (i == cur - 1 ){ t.next = null ; continue ; } t.next = tmp.get(i + 1 ); } } return root; } }
二叉树展开为链表 原题链接:https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/description/?envType=study-plan-v2&envId=top-interview-150
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 class Solution { public void flatten (TreeNode root) { while (root != null ){ if (root.left == null ){ root = root.right; }else { TreeNode insert = root.left; while (insert.right != null ){ insert = insert.right; } insert.right = root.right; root.right = root.left; root.left = null ; root = root.right; } } } }
路径总和 原题链接:https://leetcode.cn/problems/path-sum/description/?envType=study-plan-v2&envId=top-interview-150
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution { public boolean hasPathSum (TreeNode root, int targetSum) { if (root == null ){ return false ; } if (root.val == targetSum && root.left == null && root.right == null ){ return true ; } return hasPathSum(root.left,targetSum - root.val) || hasPathSum(root.right,targetSum - root.val); } }
求根节点到叶节点数字之和 原题链接:https://leetcode.cn/problems/sum-root-to-leaf-numbers/description/?envType=study-plan-v2&envId=top-interview-150
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 class Solution { int ans = 0 ; public int sumNumbers (TreeNode root) { if (root == null ){ return ans; } dfs(root,0 ); return ans; } void dfs (TreeNode node,int pre) { if (node == null ){ return ; } int cur = pre * 10 + node.val; if (node.left == null && node.right == null ){ ans += cur; } dfs(node.left,cur); dfs(node.right,cur); } }
二叉树中的最大路径和 原题链接:https://leetcode.cn/problems/binary-tree-maximum-path-sum/description/?envType=study-plan-v2&envId=top-interview-150
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class Solution { int ans = Integer.MIN_VALUE; public int maxPathSum (TreeNode root) { dfs(root); return ans; } private int dfs (TreeNode root) { if (root == null ){ return 0 ; } int left = dfs(root.left); int right = dfs(root.right); int lr = root.val + Math.max(0 ,left) + Math.max(0 ,right); int plr = root.val + Math.max(0 ,Math.max(left,right)); ans = Math.max(ans,Math.max(plr,lr)); return plr; } }
二叉搜索树迭代器 原题链接:https://leetcode.cn/problems/binary-search-tree-iterator/?envType=study-plan-v2&envId=top-interview-150
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 class BSTIterator { List<TreeNode> stk = new ArrayList <>(); public BSTIterator (TreeNode root) { dfsLeft(root); } public int next () { TreeNode node = stk.remove(stk.size() - 1 ); int res = node.val; node = node.right; dfsLeft(node); return res; } public boolean hasNext () { return !stk.isEmpty(); } private void dfsLeft (TreeNode root) { while (root != null ){ stk.add(root); root = root.left; } } }
完全二叉树的节点个数 原题链接:https://leetcode.cn/problems/count-complete-tree-nodes/description/?envType=study-plan-v2&envId=top-interview-150
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 class Solution { public int countNodes (TreeNode root) { if (root == null ){ return 0 ; } int left = countLevel(root.left); int right = countLevel(root.right); if (left == right){ return countNodes(root.right) + (1 << left); }else { return countNodes(root.left) + (1 << right); } } private int countLevel (TreeNode root) { int h = 0 ; while (root != null ){ root = root.left; h++; } return h; } }