[关闭]
@Yano 2019-09-20T02:51:52.000000Z 字数 34071 阅读 6129

LeetCode Tree 题目汇总（前 500 题）

LeetCode

https://www.zybuluo.com/Yano/note/1009816

94 Binary Tree Inorder Traversal

https://leetcode.com/problems/binary-tree-inorder-traversal/

题目描述

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree [1,null,2,3],

   1
    \
     2
    /
   3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

代码

  1.     public List<Integer> inorderTraversal(TreeNode root) {
  2.         List<Integer> ans = new ArrayList<>();
  3.         robot(root, ans);
  4.         return ans;
  5.     }
  7.     private void robot(TreeNode root, List<Integer> ans) {
  8.         if(root == null) return;
  9.         robot(root.left, ans);
  10.         ans.add(root.val);
  11.         robot(root.right, ans);
  12.     }
  1. public class Solution {
  3.     public List<Integer> inorderTraversal(TreeNode r) {
  4.         List<Integer> ans = new ArrayList<Integer>();
  6.         List<TreeNode> vector = new ArrayList<TreeNode>();
  7.         while(vector.size() != 0 || r != null){
  9.             // 一直放入左儿子（左）
  10.             while(r != null) {
  11.                 vector.add(r);
  12.                 r = r.left;
  13.             }
  15.             // 访问当前元素（中），把右儿子入栈（右）
  16.             if(vector.size() != 0) {
  17.                 r = vector.get(vector.size() - 1);
  18.                 vector.remove(vector.size() - 1);
  19.                 ans.add(r.val);
  20.                 r = r.right;
  21.             }
  22.         }
  24.         return ans;
  25.     }
  26. }

144 Binary Tree Preorder Traversal

https://leetcode.com/problems/binary-tree-preorder-traversal/

题目描述

Given a binary tree, return the preorder traversal of its nodes' values.

For example:
Given binary tree [1,null,2,3],

   1
    \
     2
    /
   3

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

代码

  1. public class Solution {
  3.     public List<Integer> preorderTraversal(TreeNode root) {
  4.         List<Integer> ans = new ArrayList<Integer>();
  6.         List<TreeNode> vector = new ArrayList<TreeNode>();
  7.         vector.add(root);
  8.         while(vector.size() != 0) {
  9.             TreeNode tmp = vector.get(vector.size() - 1);
  10.             vector.remove(vector.size() - 1);
  11.             if(tmp != null) {
  12.                 ans.add(tmp.val);
  13.                 vector.add(tmp.right);
  14.                 vector.add(tmp.left);
  15.             } 
  16.         }
  18.         return ans;
  19.     }
  20. }

145 Binary Tree Postorder Traversal

https://leetcode.com/problems/binary-tree-postorder-traversal/

题目描述

Given a binary tree, return the postorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [3,2,1].

Note: Recursive solution is trivial, could you do it iteratively?

代码

  1. public class Solution {
  3.     public static class StackNode {
  4.         TreeNode root;
  5.         boolean visit;
  6.         StackNode(TreeNode root) {
  7.             this.root = root;
  8.         }
  9.     }
  11.     public List<Integer> postorderTraversal(TreeNode root) {
  12.         List<Integer> ans = new ArrayList<Integer>();
  13.         if(root == null) return ans;
  15.         List<StackNode> vector = new ArrayList<StackNode>();
  16.         StackNode node;
  17.         vector.add(new StackNode(root));
  18.         while(vector.size() != 0) {
  19.             node = vector.get(vector.size() - 1);
  20.             vector.remove(vector.size() - 1);
  21.             if(node != null) {
  22.                 if(!node.visit) {
  23.                     node.visit = true;
  24.                     vector.add(node);
  25.                     if(node.root.right != null) vector.add(new StackNode(node.root.right));
  26.                     if(node.root.left != null) vector.add(new StackNode(node.root.left));
  27.                 } else if(node.root != null){
  28.                     ans.add(node.root.val);
  29.                 }
  30.             }
  31.         }
  33.         return ans;
  34.     }
  35. }

103 Binary Tree Zigzag Level Order Traversal

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/

题目描述

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its zigzag level order traversal as:

[
  [3],
  [20,9],
  [15,7]
]

代码

  1. class Solution {
  2.     public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
  3.         List<List<Integer>> ans = new ArrayList<>();
  4.         robot(root, 0, ans);
  5.         for(int i = 0; i < ans.size(); i++) {
  6.             if(i % 2 != 0) {
  7.                 Collections.reverse(ans.get(i));
  8.             }
  9.         }
  10.         return ans;
  11.     }
  13.     private void robot(TreeNode root, int level, List<List<Integer>> ans) {
  14.         if(root == null) return;
  15.         if(ans.size() <= level) {
  16.             ans.add(new ArrayList());
  17.         }
  19.         ans.get(level).add(root.val);
  20.         robot(root.left, level + 1, ans);
  21.         robot(root.right, level + 1, ans);
  22.     }
  23. }

105 Construct Binary Tree from Preorder and Inorder Traversal

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

题目描述

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

代码

  1. class Solution {
  2.     public TreeNode buildTree(int[] pre, int[] in) {
  3.         return robot(pre, in, 0, 0, in.length - 1);
  4.     }
  6.     private TreeNode robot(int[] pre, int[] in, int preStart, int inStart, int inEnd) {
  7.         if(preStart >= pre.length || inStart > inEnd) return null;
  8.         // 找到pos
  9.         TreeNode root = new TreeNode(pre[preStart]);
  10.         int index = 0;
  11.         for(int i = inStart; i <= inEnd; i++) {
  12.             if(in[i] == root.val) {
  13.                 index = i;
  14.                 break;
  15.             }
  16.         }
  18.         root.left = robot(pre, in, preStart + 1, inStart, index - 1);
  19.         root.right = robot(pre, in, preStart + 1 + index - inStart, index + 1, inEnd);
  20.         return root;
  21.     }
  22. }

106 Construct Binary Tree from Inorder and Postorder Traversal

https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

题目描述

Given inorder and postorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

代码

  1. class Solution {
  2.     public TreeNode buildTree(int[] in, int[] post) {
  3.         return robot(in, post, 0, in.length - 1, 0, post.length - 1);
  4.     }
  6.     private TreeNode robot(int[] in, int[] post, int inStart, int inEnd, int postStart, int postEnd) {
  7.         if(postStart > postEnd) return null;
  8.         TreeNode root = new TreeNode(post[postEnd]);
  9.         int pos = 0;// 找到pos
  10.         for(int i = inStart; i <= inEnd; i++) {
  11.             if(in[i] == root.val) {
  12.                 pos = i;
  13.                 break;
  14.             }
  15.         }
  17.         root.left = robot(in, post, inStart, pos - 1, postStart, postStart + pos - inStart - 1);
  18.         root.right = robot(in, post, pos + 1, inEnd, postEnd + pos - inEnd, postEnd - 1);
  19.         return root;
  20.     }
  21. }

96 Unique Binary Search Trees

https://leetcode.com/problems/unique-binary-search-trees/

题目描述

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
Given n = 3, there are a total of 5 unique BST's.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

代码

  1.     public int numTrees(int n) {
  2.         int[] ans = new int[n + 2];
  3.         ans[0] = 1; ans[1] = 1; ans[2] = 2;
  4.         // f(n) = f(0)*f(n-1) + f(1)*f(n-2) + ……
  5.         for(int i = 3; i <= n; i++) {
  6.             for(int j = 0; j <= i - 1; j++) {
  7.                 ans[i] += ans[j] * ans[i - j - 1];
  8.             }
  9.         }
  10.         return ans[n];
  11.     }

95 Unique Binary Search Trees II

https://leetcode.com/problems/unique-binary-search-trees-ii/

题目描述

Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1...n.

For example,
Given n = 3, your program should return all 5 unique BST's shown below.

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

代码

  1. class Solution {
  2.     public List<TreeNode> generateTrees(int n) {
  3.         if(n <= 0) return new ArrayList<>();
  4.         return build(1, n);
  5.     }
  7.     private List<TreeNode> build(int start, int end) {
  8.         List<TreeNode> roots = new ArrayList<>();       
  9.         if(start > end) {           
  10.             // null也要放入，否则下面的双重循环进不去
  11.             roots.add(null);
  12.             return roots;
  13.         }
  14.         if(start == end) {
  15.             roots.add(new TreeNode(start));
  16.             return roots;
  17.         }
  18.         for(int i = start; i <= end; i++) {
  19.             List<TreeNode> leftList = build(start, i - 1);
  20.             List<TreeNode> rightList = build(i + 1, end);
  21.             for(TreeNode left : leftList) {             
  22.                 for(TreeNode right : rightList) {
  23.                     TreeNode root = new TreeNode(i);
  24.                     root.left = left;
  25.                     root.right = right;
  26.                     roots.add(root);
  27.                 }
  28.             }
  29.         }
  30.         return roots;
  31.     }
  32. }

98 Validate Binary Search Tree

https://leetcode.com/problems/validate-binary-search-tree/

题目描述

Given a binary tree, determine if it is a valid binary search tree (BST).

Assume a BST is defined as follows:

The left subtree of a node contains only nodes with keys less than the node's key.
The right subtree of a node contains only nodes with keys greater than the node's key.
Both the left and right subtrees must also be binary search trees.

Example 1:

    2
   / \
  1   3

Binary tree [2,1,3], return true.

Example 2:

    1
   / \
  2   3

Binary tree [1,2,3], return false.

代码

  1.     public boolean isValidBST(TreeNode root) {
  2.         // 用long型
  3.         return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
  4.     }
  5.     private boolean isValidBST(TreeNode root, long min, long max) {
  6.         if(root == null) return true;
  7.         if(root.val >= max || root.val <= min) return false;
  8.         return isValidBST(root.left, min, root.val) && isValidBST(root.right, root.val, max);
  9.     }

99 Recover Binary Search Tree

https://leetcode.com/problems/recover-binary-search-tree/

题目描述

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:
A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

代码

  1. class Solution {
  3.     TreeNode first = null, second = null;
  4.     TreeNode pre = new TreeNode(Integer.MIN_VALUE);
  6.     public void recoverTree(TreeNode root) {
  7.         if(root == null) return;
  8.         robot(root);
  9.         if(first != null && second != null) {
  10.             int tmp = first.val;
  11.             first.val = second.val;
  12.             second.val = tmp;
  13.         }
  14.     }
  16.     private void robot(TreeNode root) {
  17.         if(root == null) return;
  18.         robot(root.left);
  19.         // 找到交换的两个节点
  20.         if(first == null && pre.val >= root.val) {
  21.             first = pre;
  22.         }
  24.         if(first != null && pre.val >= root.val) {
  25.             second = root;
  26.         }
  27.         pre = root;
  28.         robot(root.right);
  29.     }
  30. }

450 Delete Node in a BST

https://leetcode.com/problems/delete-node-in-a-bst/

题目描述

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

Search for a node to remove.
If the node is found, delete the node.

Note: Time complexity should be O(height of tree).

Example:

root = [5,3,6,2,4,null,7]
key = 3

    5
   / \
  3   6
 / \   \
2   4   7

Given key to delete is 3. So we find the node with value 3 and delete it.

One valid answer is [5,4,6,2,null,null,7], shown in the following BST.

    5
   / \
  4   6
 /     \
2       7

Another valid answer is [5,2,6,null,4,null,7].

    5
   / \
  2   6
   \   \
    4   7

代码

  1. class Solution {
  2.     TreeNode target = null;
  3.     TreeNode targetParent = null;
  4.     public TreeNode deleteNode(TreeNode root, int key) {
  5.         // 1. 找到目标节点
  6.         find(root, key);
  7.         if(target == null) return root;
  8.         // 2. update
  9.         if(target == root) {
  10.             if(target.left == null && target.right == null) return null;
  11.             targetParent = target.left == null ? target.right : target.left;
  12.             if(target.left != null) {
  13.                 getMaxNode(targetParent).right = target.right;
  14.             } else {
  15.                 // target.right = null;
  16.             }
  17.             return targetParent;
  18.         }
  20.         if(target.left != null) {
  21.             getMaxNode(target.left).right = target.right;
  22.             adjust(targetParent, target, target.left);
  23.         } else if(target.right != null) {
  24.             adjust(targetParent, target, target.right);
  25.         } else {
  26.             adjust(targetParent, target, null);
  27.         }
  28.         return root;
  29.     }
  31.     private void adjust(TreeNode targetParent, TreeNode target, TreeNode replace) {
  32.         if(targetParent.left == target) targetParent.left = replace;
  33.         if(targetParent.right == target) targetParent.right = replace;
  34.     }
  36.     private TreeNode getMaxNode(TreeNode root) {
  37.         if(root == null) return null;
  38.         while(root.right != null) {
  39.             root = root.right;
  40.         }
  41.         return root;
  42.     }
  44.     private void find(TreeNode root, int key) {
  45.         if(root == null) return;
  46.         if(root.left != null && root.left.val == key) {
  47.             targetParent = root;
  48.         }
  49.         if(root.right != null && root.right.val == key)  {
  50.             targetParent = root;
  51.         }
  52.         if(root.val == key) {
  53.             target = root;
  54.             return;
  55.         }
  56.         find(root.left, key);
  57.         find(root.right, key);
  58.     }
  59. }

230 Kth Smallest Element in a BST

https://leetcode.com/problems/kth-smallest-element-in-a-bst/

题目描述

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note:
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.

Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

Credits:Special thanks to @ts for adding this problem and creating all test cases.

代码

  1. class Solution {
  2.     int ans = 0;
  3.     int count = 0;
  5.     public int kthSmallest(TreeNode root, int k) {
  6.         count = k;
  7.         robot(root);
  8.         return ans;
  9.     }
  11.     private void robot(TreeNode root) {
  12.         if(root == null) return;
  14.         robot(root.left);
  15.         if(--count == 0) {
  16.             ans = root.val;
  17.             return;
  18.         }
  19.         robot(root.right);
  20.     }
  21. }

100 Same Tree

https://leetcode.com/problems/same-tree/

题目描述

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Example 1:

Input:     1         1
          / \       / \
         2   3     2   3

        [1,2,3],   [1,2,3]

Output: true

Example 2:

Input:     1         1
          /           \
         2             2

        [1,2],     [1,null,2]

Output: false

Example 3:

Input:     1         1
          / \       / \
         2   1     1   2

        [1,2,1],   [1,1,2]

Output: false

代码

  1. class Solution {
  2.     public boolean isSameTree(TreeNode p, TreeNode q) {
  3.         if(p == null && q == null) return true;
  4.         if(p == null || q == null) return false;
  5.         if(p.val != q.val) return false;
  6.         return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
  7.     }
  8. }

101 Symmetric Tree

https://leetcode.com/problems/symmetric-tree/

题目描述

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

    1
   / \
  2   2
 / \ / \
3  4 4  3

But the following [1,2,2,null,3,null,3] is not:

    1
   / \
  2   2
   \   \
   3    3

Note:
Bonus points if you could solve it both recursively and iteratively.

代码

  1. class Solution {
  2.     public boolean isSymmetric(TreeNode root) {
  3.         if(root == null) return true;
  4.         return isSymmetric(root.left, root.right);
  5.     }
  6.     private boolean isSymmetric(TreeNode p, TreeNode q) {
  7.         if(p == null && q == null) return true;
  8.         if(p == null || q == null) return false;
  9.         if(p.val != q.val) return false;
  10.         return isSymmetric(p.left, q.right) && isSymmetric(p.right, q.left);
  11.     }
  12. }

102 Binary Tree Level Order Traversal

https://leetcode.com/problems/binary-tree-level-order-traversal/

题目描述

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

[
  [3],
  [9,20],
  [15,7]
]

代码

  1. class Solution {
  2.     public List<List<Integer>> levelOrder(TreeNode root) {
  3.         List<List<Integer>> ans = new ArrayList<>();
  4.         robot(root, 0, ans);
  5.         return ans;
  6.     }
  8.     private void robot(TreeNode root, int level, List<List<Integer>> ans) {
  9.         if(root == null) return;
  10.         if(ans.size() <= level) {
  11.             ans.add(new ArrayList());
  12.         }
  14.         ans.get(level).add(root.val);
  15.         robot(root.left, level + 1, ans);
  16.         robot(root.right, level + 1, ans);
  17.     }
  18. }

107 Binary Tree Level Order Traversal II

https://leetcode.com/problems/binary-tree-level-order-traversal-ii/

题目描述

Given a binary tree, return the bottom-up level order traversal of its nodes' values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]

代码

  1. class Solution {
  2.     public List<List<Integer>> levelOrderBottom(TreeNode root) {
  3.         List<List<Integer>> ans = new ArrayList<>();
  4.         robot(root, 0, ans);
  5.         Collections.reverse(ans);
  6.         return ans;
  7.     }
  9.     private void robot(TreeNode root, int level, List<List<Integer>> ans) {
  10.         if(root == null) return;
  11.         if(ans.size() <= level) {
  12.             ans.add(new ArrayList());
  13.         }
  15.         ans.get(level).add(root.val);
  16.         robot(root.left, level + 1, ans);
  17.         robot(root.right, level + 1, ans);
  18.     }
  19. }

104 Maximum Depth of Binary Tree

https://leetcode.com/problems/maximum-depth-of-binary-tree/

题目描述

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

代码

  1. class Solution {
  2.     public int maxDepth(TreeNode root) {
  3.         if(root == null) return 0;
  4.         int left = maxDepth(root.left);
  5.         int right = maxDepth(root.right);
  6.         return (left == 0 || right == 0) ? (left + right + 1) : Math.max(left, right) + 1;
  7.     }
  8. }

108 Convert Sorted Array to Binary Search Tree

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

题目描述

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5

代码

  1. class Solution {
  2.     public TreeNode sortedArrayToBST(int[] nums) {
  3.         if(nums == null || nums.length == 0) return null;
  4.         return robot(nums, 0, nums.length - 1);
  5.     }
  7.     private TreeNode robot(int[] nums, int start, int end) {
  8.         if(start > end) return null;
  9.         int mid = start + (end - start) / 2;
  10.         TreeNode root = new TreeNode(nums[mid]);
  11.         root.left = robot(nums, start, mid - 1);
  12.         root.right = robot(nums, mid + 1, end);
  13.         return root;
  14.     }
  15. }

110 Balanced Binary Tree

https://leetcode.com/problems/balanced-binary-tree/

题目描述

Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

代码

  1. class Solution {
  2.     public boolean isBalanced(TreeNode root) {
  3.         if(root == null) return true;
  4.         int left = depth(root.left);
  5.         int right = depth(root.right);
  6.         return Math.abs(left - right) <= 1 && isBalanced(root.left) && isBalanced(root.right);
  7.     }
  9.     private int depth(TreeNode root) {
  10.         if(root == null) return 0;
  11.         return Math.max(depth(root.left), depth(root.right)) + 1;
  12.     }
  13. }

173 Binary Search Tree Iterator

https://leetcode.com/problems/binary-search-tree-iterator/

题目描述

Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST.

Calling next() will return the next smallest number in the BST.

Note: next() and hasNext() should run in average O(1) time and uses O(h) memory, where h is the height of the tree.

Credits:Special thanks to @ts for adding this problem and creating all test cases.

代码

  1. public class BSTIterator {
  3.     List<TreeNode> vector = new ArrayList<TreeNode>();
  4.     TreeNode curr = null;
  6.     public BSTIterator(TreeNode root) {
  7.         curr = root;
  8.         // 一直放入左儿子（左）
  9.         while(curr != null) {
  10.             vector.add(curr);
  11.             curr = curr.left;
  12.         }
  13.     }
  15.     /** @return whether we have a next smallest number */
  16.     public boolean hasNext() {
  17.         return vector.size() != 0 || curr != null;
  18.     }
  20.     /** @return the next smallest number */
  21.     public int next() {
  22.         // 一直放入左儿子（左）
  23.         while(curr != null) {
  24.             vector.add(curr);
  25.             curr = curr.left;
  26.         }
  28.         int ans = 0;
  30.         // 访问当前元素（中），把右儿子入栈（右）
  31.         if(vector.size() != 0) {
  32.             curr = vector.get(vector.size() - 1);
  33.             vector.remove(vector.size() - 1);
  34.             ans = curr.val;
  35.             curr = curr.right;
  36.         }
  38.         return ans;
  39.     }
  40. }
  42. /**
  43.  * Your BSTIterator will be called like this:
  44.  * BSTIterator i = new BSTIterator(root);
  45.  * while (i.hasNext()) v[f()] = i.next();
  46.  */

111 Minimum Depth of Binary Tree

https://leetcode.com/problems/minimum-depth-of-binary-tree/

题目描述

Given a binary tree, find its minimum depth.

The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

代码

  1. class Solution {
  2.     public int minDepth(TreeNode root) {
  3.         if(root == null) return 0;
  4.         int left = minDepth(root.left);
  5.         int right = minDepth(root.right);
  6.         return (left == 0 || right == 0) ? (left + right + 1) : Math.min(left, right) + 1;
  7.     }
  8. }

112 Path Sum

https://leetcode.com/problems/path-sum/

题目描述

Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.

For example:
Given the below binary tree and sum = 22,

          5
         / \
        4   8
       /   / \
      11  13  4
     /  \      \
    7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.

代码

  1. class Solution {
  2.     public boolean hasPathSum(TreeNode root, int sum) {
  3.         if(root == null) return false;
  4.         if(root.left == null && root.right == null && sum - root.val == 0) return true;
  5.         return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
  6.     }
  7. }

113 Path Sum II

https://leetcode.com/problems/path-sum-ii/

题目描述

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree and sum = 22,

          5
         / \
        4   8
       /   / \
      11  13  4
     /  \    / \
    7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

代码

  1. class Solution {
  2.     public List<List<Integer>> pathSum(TreeNode root, int sum) {
  3.         List<List<Integer>> ans = new ArrayList<>();
  4.         robot(root, sum, ans, new ArrayList<>());
  5.         return ans;
  6.     }
  8.     private void robot(TreeNode root, int sum, List<List<Integer>> ans, List<Integer> tmp) {
  9.         if(root == null) return;
  10.         tmp.add(root.val);
  11.         if(root.left == null && root.right == null && sum == root.val) {
  12.             ans.add(new ArrayList(tmp));
  13.             tmp.remove(tmp.size() - 1);
  14.             return;
  15.         }
  16.         robot(root.left, sum - root.val, ans, tmp);
  17.         robot(root.right, sum - root.val, ans, tmp);
  18.         tmp.remove(tmp.size() - 1);
  19.     }
  20. }

437 Path Sum III

https://leetcode.com/problems/path-sum-iii/

题目描述

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards
(traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

代码

  1. class Solution {
  2.     int ans = 0;
  3.     public int pathSum(TreeNode root, int sum) {
  4.         // 以每个节点开始做算法
  5.         robot(root, sum);
  6.         return ans;
  7.     }
  9.     private void robot(TreeNode root, int sum) {
  10.         if(root == null) return;
  11.         robot(root.left, sum);
  12.         // core，以 root 为起点，遍历所有节点求和
  13.         countPath(root, sum);
  14.         robot(root.right, sum);
  15.     }
  17.     private void countPath(TreeNode root, int left) {
  18.         if(root == null) return;
  19.         left -= root.val;
  20.         if(left == 0) ans++;
  21.         countPath(root.left, left);
  22.         countPath(root.right, left);
  23.     }
  24. }

114 Flatten Binary Tree to Linked List

https://leetcode.com/problems/flatten-binary-tree-to-linked-list/

题目描述

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

     1
    / \
   2   5
  / \   \
 3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

click to show hints.

Hints:
If you notice carefully in the flattened tree, each node's right child points to the next node of a pre-order traversal.

代码

  1. public class Solution {
  3.     public void flatten(TreeNode root) {
  4.         if(root == null) return;
  5.         flatten(root.left);
  6.         flatten(root.right);
  8.         TreeNode tmp = root.right;
  9.         root.right = root.left;
  10.         root.left = null;
  11.         // root.right 已经是原来的 root.left
  12.         while(root.right != null) root = root.right;
  13.         root.right = tmp;
  14.     }
  15. }

116 Populating Next Right Pointers in Each Node

https://leetcode.com/problems/populating-next-right-pointers-in-each-node/

题目描述

Given a binary tree

struct TreeLinkNode {
  TreeLinkNode *left;
  TreeLinkNode *right;
  TreeLinkNode *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Note:

You may only use constant extra space.
You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,
Given the following perfect binary tree,

     1
   /  \
  2    3
 / \  / \
4  5  6  7

After calling your function, the tree should look like:

     1 -> NULL
   /  \
  2 -> 3 -> NULL
 / \  / \
4->5->6->7 -> NULL

代码

  1. public class Solution {
  3.     public void connect(TreeLinkNode root) {
  4.        if(root == null) return;
  6.         if(root.left != null) {
  7.             root.left.next = root.right;
  8.             if(root.next != null) {
  9.                 root.right.next = root.next.left;
  10.             }
  11.         }
  13.         connect(root.left);
  14.         connect(root.right);
  15.     }
  16. }

117 Populating Next Right Pointers in Each Node II

https://leetcode.com/problems/populating-next-right-pointers-in-each-node-ii/

题目描述

Follow up for problem "Populating Next Right Pointers in Each Node".
What if the given tree could be any binary tree? Would your previous solution still work?

Note:
You may only use constant extra space.

For example,
Given the following binary tree,

     1
   /  \
  2    3
 / \    \
4   5    7

After calling your function, the tree should look like:

     1 -> NULL
   /  \
  2 -> 3 -> NULL
 / \    \
4-> 5 -> 7 -> NULL

代码

  1. public class Solution {
  2.     public void connect(TreeLinkNode root) {
  3.         if(root == null) return;
  4.         if(root.left == null && root.right == null) return;
  6.         TreeLinkNode p = root.next;
  7.         while(p != null) {
  8.             if(p.left != null) {
  9.                 p = p.left;
  10.                 break;
  11.             }
  12.             if(p.right != null) {
  13.                 p = p.right;
  14.                 break;
  15.             }
  16.             p = p.next;
  17.         }
  19.         if(root.right != null) root.right.next = p;
  20.         if(root.left != null) root.left.next = root.right == null ? p : root.right;
  22.         // 先右子树，因为 next 节点依赖右边
  23.         connect(root.right);
  24.         connect(root.left);
  25.     }
  27. }

124 Binary Tree Maximum Path Sum

https://leetcode.com/problems/binary-tree-maximum-path-sum/

题目描述

Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

For example:
Given the below binary tree,

   1
  / \
 2   3

Return 6.

代码

  1. class Solution {
  2.     int max = Integer.MIN_VALUE;
  4.     public int maxPathSum(TreeNode root) {
  5.         robot(root);
  6.         return max;
  7.     }
  9.     private int robot(TreeNode root) {
  10.         if(root == null) return 0;
  11.         int left = robot(root.left);
  12.         int right = robot(root.right);
  13.         int ans = root.val;
  14.         if(Math.max(left, right) > 0) {
  15.             ans += Math.max(left, right);
  16.         }
  17.         max = Math.max(max, root.val);
  18.         max = Math.max(max, left + root.val);
  19.         max = Math.max(max, right + root.val);
  20.         max = Math.max(max, left + right + root.val);
  21.         return ans;
  22.     }
  23. }

129 Sum Root to Leaf Numbers

https://leetcode.com/problems/sum-root-to-leaf-numbers/

题目描述

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.
An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.

Return the sum = 12 + 13 = 25.

代码

  1. class Solution {
  2.     public int sumNumbers(TreeNode root) {
  3.         return robot(root, 0);
  4.     }
  6.     private int robot(TreeNode root, int sum) {
  7.         if(root == null) return 0;
  8.         sum = sum * 10 + root.val;
  9.         if(root.left == null && root.right == null) return sum;
  10.         return robot(root.left, sum) + robot(root.right, sum);
  11.     }
  12. }

404 Sum of Left Leaves

https://leetcode.com/problems/sum-of-left-leaves/

题目描述

Find the sum of all left leaves in a given binary tree.

Example:

    3
   / \
  9  20
    /  \
   15   7

There are two left leaves in the binary tree, with values 9 and 15 respectively. Return 24.

代码

  1. class Solution {
  2.     int ans = 0;
  3.     public int sumOfLeftLeaves(TreeNode root) {
  4.         robot(root, false);
  5.         return ans;
  6.     }
  8.     private void robot(TreeNode root, boolean isLeft) {
  9.         if(root == null) return;
  10.         if(root.left == null && root.right == null && isLeft) {
  11.             ans += root.val;
  12.             return;
  13.         } 
  14.         robot(root.left, true);
  15.         robot(root.right, false);
  16.     }
  17. }

199 Binary Tree Right Side View

https://leetcode.com/problems/binary-tree-right-side-view/

题目描述

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:
Given the following binary tree,

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4].

Credits:Special thanks to @amrsaqr for adding this problem and creating all test cases.

代码

  1. class Solution {
  2.     public List<Integer> rightSideView(TreeNode root) {
  3.         List<Integer> ans = new ArrayList<>();
  4.         robot(root, ans, 0);
  5.         return ans;
  6.     }
  8.     private void robot(TreeNode root, List<Integer> ans, int height) {
  9.         if(root == null) return;
  10.         if(ans.size() <= height) {
  11.             ans.add(root.val);
  12.         }
  13.         ans.set(height, root.val);
  14.         robot(root.left, ans, height + 1);
  15.         robot(root.right, ans, height + 1);  
  16.     }
  17. }

222 Count Complete Tree Nodes

https://leetcode.com/problems/count-complete-tree-nodes/

题目描述

Given a complete binary tree, count the number of nodes.

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

代码

  1. class Solution {
  2.     public int countNodes(TreeNode root) {
  3.         if(root == null) return 0;
  4.         int left = leftHeight(root);
  5.         int right = rightHeight(root);
  7.         if(left == right) return (1 << left) - 1;
  8.         return countNodes(root.left) + countNodes(root.right) + 1;
  9.     }
  11.     private int leftHeight(TreeNode root) {
  12.         int depth = 0;
  13.         while(root != null) {
  14.             depth++;
  15.             root = root.left;
  16.         }
  17.         return depth;
  18.     }
  20.     private int rightHeight(TreeNode root) {
  21.         int depth = 0;
  22.         while(root != null) {
  23.             depth++;
  24.             root = root.right;
  25.         }
  26.         return depth;
  27.     }
  28. }

226 Invert Binary Tree

https://leetcode.com/problems/invert-binary-tree/

题目描述

Invert a binary tree.

     4
   /   \
  2     7
 / \   / \
1   3 6   9

to

     4
   /   \
  7     2
 / \   / \
9   6 3   1

Trivia:
This problem was inspired by this original tweet by Max Howell:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.

代码

  1. public class Solution {
  2.     public TreeNode invertTree(TreeNode root) {
  3.         if(root == null) return root;
  4.         TreeNode tmp = root.left;
  5.         root.left = root.right;
  6.         root.right = tmp;
  7.         invertTree(root.left);
  8.         invertTree(root.right);
  9.         return root;
  10.     }
  11. }

235 Lowest Common Ancestor of a Binary Search Tree

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

题目描述

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______6______
       /              \
    ___2__          ___8__
   /      \        /      \
   0      _4       7       9
         /  \
         3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

代码

  1. class Solution {
  2.     TreeNode ans = null;
  4.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  5.         if(root == null || p == null || q == null) return null;
  6.         int min = Math.min(p.val, q.val);
  7.         int max = Math.max(p.val, q.val);
  8.         robot(root, min, max);
  9.         return ans;
  10.     }
  12.     private void robot(TreeNode root, int min, int max) {
  13.         if(root == null) return;
  14.         robot(root.left, min, max);
  15.         if(root.val <= max && root.val >= min) {
  16.             ans = root;
  17.             return;
  18.         }
  19.         robot(root.right, min, max);
  20.     }
  21. }

236 Lowest Common Ancestor of a Binary Tree

https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/

题目描述

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

代码

  1. public class Solution {
  2.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  3.         if(root == null || root == p || root == q) {
  4.             return root;
  5.         }
  6.         TreeNode left = lowestCommonAncestor(root.left, p, q);
  7.         TreeNode right = lowestCommonAncestor(root.right, p, q);
  8.         if(left != null && right != null) return root;
  9.         return left == null ? right : left;
  10.     }
  11. }

257 Binary Tree Paths

https://leetcode.com/problems/binary-tree-paths/

题目描述

Given a binary tree, return all root-to-leaf paths.

For example, given the following binary tree:

   1
 /   \
2     3
 \
  5

All root-to-leaf paths are:

["1->2->5", "1->3"]

Credits:Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

代码

  1. class Solution {
  2.     public List<String> binaryTreePaths(TreeNode root) {
  3.         List<String> ans = new ArrayList<>();
  4.         robot(root, ans, "");
  5.         return ans;
  6.     }
  8.     private void robot(TreeNode root, List<String> ans, String path) {
  9.         if(root == null) return;
  10.         if(root.left == null && root.right == null) {
  11.             ans.add(path + root.val);
  12.             return;
  13.         }
  14.         robot(root.left, ans, path + root.val + "->");
  15.         robot(root.right, ans, path + root.val + "->");
  16.     }
  17. }

297 Serialize and Deserialize Binary Tree

https://leetcode.com/problems/serialize-and-deserialize-binary-tree/

题目描述

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

For example, you may serialize the following tree

    1
   / \
  2   3
     / \
    4   5

as "[1,2,3,null,null,4,5]", just the same as how LeetCode OJ serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

Credits:Special thanks to @Louis1992 for adding this problem and creating all test cases.

代码

  1. public class Codec {
  3.     private static final String NULL = "*";
  4.     private static final String SEP  = ",";
  6.     // Encodes a tree to a single string.
  7.     public String serialize(TreeNode root) {
  8.         StringBuilder ans = new StringBuilder();
  9.         Queue<TreeNode> queue = new LinkedList<>();
  10.         queue.add(root);
  11.         while(!queue.isEmpty()) {
  12.             TreeNode node = queue.poll();
  13.             if(node == null) {
  14.                 ans.append(NULL);
  15.             } else {
  16.                 ans.append(node.val);
  17.                 queue.add(node.left);
  18.                 queue.add(node.right);
  19.             }
  20.             ans.append(SEP);
  21.         }
  22.         return ans.substring(0, ans.length() - 1).toString();
  23.     }
  25.     // Decodes your encoded data to tree.
  26.     public TreeNode deserialize(String data) {
  27.         if(data == null) return null;
  28.         String[] vals = data.split(",");
  29.         if(vals.length == 0 || NULL.equals(vals[0])) return null;
  31.         Queue<TreeNode> queue = new LinkedList<>();
  32.         TreeNode root = buildNode(vals[0]);
  33.         queue.add(root);
  34.         TreeNode node = null;
  36.         for(int i = 1; i < vals.length; i += 2) {
  37.             while((node = queue.poll()) == null);
  38.             node.left = buildNode(vals[i]);
  39.             node.right = buildNode(i + 1 < vals.length ? vals[i + 1] : NULL);
  40.             queue.add(node.left);
  41.             queue.add(node.right);
  42.         }
  44.         return root;
  45.     }
  47.     private TreeNode buildNode(String val) {
  48.         if(val == null || val.equals(NULL)) return null;
  49.         return new TreeNode(Integer.valueOf(val));
  50.     }
  51. }
  53. // Your Codec object will be instantiated and called as such:
  54. // Codec codec = new Codec();
  55. // codec.deserialize(codec.serialize(root));

递归

  1. public class Codec {
  3.     // Encodes a tree to a single string.
  4.     public String serialize(TreeNode root) {
  5.         StringBuilder sb = new StringBuilder();
  6.         robot(root, sb);
  7.         return sb.toString();
  8.     }
  10.     public void robot(TreeNode root, StringBuilder sb) {
  11.         if(root == null) {
  12.             sb.append("X").append(",");
  13.         } else {
  14.             sb.append(root.val + "").append(",");
  15.             robot(root.left, sb);
  16.             robot(root.right, sb);
  17.         }
  18.     }
  20.     // Decodes your encoded data to tree.
  21.     public TreeNode deserialize(String data) {
  22.         Deque<String> nodes = new LinkedList<>();
  23.         nodes.addAll(Arrays.asList(data.split(",")));
  24.         return buildTree(nodes);
  25.     }
  27.     public TreeNode buildTree(Deque<String> nodes) {
  28.         String val = nodes.remove();
  29.         if(val.equals("X")) {
  30.             return null;
  31.         } else {
  32.             TreeNode root = new TreeNode(Integer.valueOf(val));
  33.             root.left = buildTree(nodes);
  34.             root.right = buildTree(nodes);
  35.             return root;
  36.         }
  37.     }
  38. }
  40. // Your Codec object will be instantiated and called as such:
  41. // Codec codec = new Codec();
  42. // codec.deserialize(codec.serialize(root));

449 Serialize and Deserialize BST

https://leetcode.com/problems/serialize-and-deserialize-bst/

题目描述

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure.

The encoded string should be as compact as possible.

Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.

代码

  1. public class Codec {
  3.     // Encodes a tree to a single string.
  4.     public String serialize(TreeNode root) {
  5.         List<Integer> preList = new ArrayList<>();
  6.         robot(root, preList);
  7.         return preList.toString().substring(1, preList.toString().length() - 1);
  8.     }
  10.     private void robot(TreeNode root, List<Integer> list) {
  11.         if(root == null) return;
  12.         list.add(root.val);
  13.         robot(root.left, list);
  14.         robot(root.right, list);
  15.     }
  17.     // Decodes your encoded data to tree.
  18.     public TreeNode deserialize(String data) {
  19.         if(data == null || data.trim().equals("")) return null;
  20.         int[] pre = parse(data);
  21.         int[] in = pre.clone();
  22.         Arrays.sort(in);
  23.         return buildTree(pre, in);
  24.     }
  26.     private int[] parse(String data) {
  27.         int[] array = new int[data.split(",").length];
  28.         int i = 0;
  29.         for(String val : data.split(",")) {
  30.             array[i++] = Integer.valueOf(val.trim());
  31.         }
  32.         return array;
  33.     }
  35.     private TreeNode build(int preStart, int inStart, int inEnd, int[] pre, int[] in) {
  36.         if(preStart >= pre.length || inStart > inEnd) {
  37.             return null;
  38.         }
  39.         TreeNode root = new TreeNode(pre[preStart]);
  41.         int inIndex = 0;
  42.         for(int i = inStart; i <= inEnd; i++) {
  43.             if(in[i] == root.val) {
  44.                 inIndex = i;
  45.                 break;
  46.             }
  47.         }
  49.         root.left = build(preStart + 1, inStart, inIndex - 1, pre, in);
  50.         root.right = build(preStart + inIndex - inStart + 1, inIndex + 1, inEnd, pre, in);
  51.         return root;
  52.     }
  54.     private TreeNode buildTree(int[] preorder, int[] inorder) {
  55.         return build(0, 0, inorder.length - 1, preorder, inorder);
  56.     }
  57. }
  59. // Your Codec object will be instantiated and called as such:
  60. // Codec codec = new Codec();
  61. // codec.deserialize(codec.serialize(root));

337 House Robber III

https://leetcode.com/problems/house-robber-iii/

题目描述

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the "root." Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that "all houses in this place forms a binary tree". It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

     3
    / \
   2   3
    \   \ 
     3   1

Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.

Example 2:

     3
    / \
   4   5
  / \   \ 
 1   3   1

Maximum amount of money the thief can rob = 4 + 5 = 9.

Credits:Special thanks to @dietpepsi for adding this problem and creating all test cases.

代码

  1. class Solution {
  2.     public int rob(TreeNode root) {
  3.         if(root == null) return 0;
  4.         return Math.max(robIn(root), robEx(root));
  5.     }
  7.     private int robIn(TreeNode root) {
  8.         if(root == null) return 0;
  9.         return root.val + robEx(root.left) + robEx(root.right);
  10.     }
  12.     private int robEx(TreeNode root) {
  13.         if(root == null) return 0;
  14.         // 可以不抢下一个节点
  15.         return rob(root.left) + rob(root.right);
  16.     }
  17. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注