[关闭]
@Yano 2019-09-20T10:56:40.000000Z 字数 27264 阅读 8718

LeetCode之Tree题目汇总

LeetCode

公众号

coding 笔记、点滴记录，以后的文章也会同步到公众号（Coding Insight）中，希望大家关注^_^

https://github.com/LjyYano/Thinking_in_Java_MindMapping

LeetCode 题目汇总

LeetCode之Array题目汇总
LeetCode之Hash Table题目汇总
LeetCode之Linked List题目汇总
LeetCode之Math题目汇总
LeetCode之String题目汇总
LeetCode之Binary Search题目汇总
LeetCode之Divide and Conquer题目汇总
LeetCode之Dynamic Programming题目汇总
LeetCode之Backtracing题目汇总
LeetCode之Stack题目汇总
LeetCode之Sort题目汇总
LeetCode之Bit Manipulation题目汇总
LeetCode之Tree题目汇总
LeetCode之Depth-first Search题目汇总
LeetCode之Breadth-first Search题目汇总
LeetCode之Graph题目汇总
LeetCode之Trie题目汇总
LeetCode之Design题目汇总

文章目录：

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

核心代码：

  1.         return Math.abs(height(root.left) - height(root.right)) <= 1
  2.                 && isBalanced(root.left) && isBalanced(root.right);
  1.     public boolean isBalanced(TreeNode root) {
  3.         if (root == null) {
  4.             return true;
  5.         }
  7.         return Math.abs(height(root.left) - height(root.right)) <= 1
  8.                 && isBalanced(root.left) && isBalanced(root.right);
  10.     }
  12.     int height(TreeNode node) {
  14.         if (node == null) {
  15.             return 0;
  16.         }
  18.         return Math.max(height(node.left), height(node.right)) + 1;
  19.     }

Binary Tree Inorder Traversal

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

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

  1.    1
  2.     \
  3.      2
  4.     /
  5.    3

return [1,3,2].

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

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

  1.     List<Integer> rt = new ArrayList<Integer>();
  3.     public List<Integer> inorderTraversal(TreeNode root) {
  5.         rt.clear();
  6.         inorder(root);
  7.         return rt;
  8.     }
  10.     void inorder(TreeNode node) {
  12.         if (node == null) {
  13.             return;
  14.         }
  16.         inorder(node.left);
  17.         rt.add(node.val);
  18.         inorder(node.right);
  19.     }

Binary Tree Preorder Traversal

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

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

  1.    1
  2.     \
  3.      2
  4.     /
  5.    3

return [1,2,3].

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

  1.     public List<Integer> preorderTraversal(TreeNode root) {
  3.         List<Integer> rt = new ArrayList<Integer>();
  5.         if (root == null) {
  6.             return rt;
  7.         }
  9.         Stack<TreeNode> stack = new Stack<TreeNode>();
  10.         TreeNode p = root;
  12.         while (p != null || !stack.empty()) {
  14.             while (p != null) {
  15.                 rt.add(p.val);
  16.                 stack.push(p);
  17.                 p = p.left;
  18.             }
  20.             if (!stack.empty()) {
  21.                 p = stack.pop();
  22.                 p = p.right;
  23.             }
  24.         }
  26.         return rt;
  27.     }

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.    1
  2.     \
  3.      2
  4.     /
  5.    3

return [3,2,1].

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

  1.     public class PostTreeNode {
  2.         TreeNode node;
  3.         boolean first;
  4.     }
  6.     public List<Integer> postorderTraversal(TreeNode root) {
  8.         List<Integer> rt = new ArrayList<Integer>();
  10.         if (root == null) {
  11.             return rt;
  12.         }
  14.         Stack<PostTreeNode> stack = new Stack<PostTreeNode>();
  15.         TreeNode p = root;
  16.         PostTreeNode t;
  18.         while (p != null || !stack.empty()) {
  20.             while (p != null) {
  22.                 // 新建一个结点，这个结点包含一个布尔值first
  23.                 // 用来判断是否是第一次入栈
  24.                 PostTreeNode post = new PostTreeNode();
  25.                 post.node = p;
  26.                 post.first = true;
  27.                 stack.push(post);
  28.                 p = p.left;
  29.             }
  31.             if (!stack.empty()) {
  33.                 t = stack.pop();
  35.                 // 如果结点第一次出栈，再次入栈，将first置为false
  36.                 if (t.first == true) {
  37.                     t.first = false;
  38.                     stack.push(t);
  39.                     p = t.node.right;
  40.                 } else {
  41.                     rt.add(t.node.val);
  42.                     p = null;
  43.                 }
  44.             }
  45.         }
  47.         return rt;
  48.     }

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,#,#,15,7},

  1.     3
  2.    / \
  3.   9  20
  4.     /  \
  5.    15   7

return its level order traversal as:

  1. [
  2.   [3],
  3.   [9,20],
  4.   [15,7]
  5. ]

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

1. 通过统计每一行的结点数

定义两个变量，toBePrinted和nextLevel。

toBePrinted：当前待打印结点的数量 
nextLevel：下一层的结点数量

通过Deque来进行统计。

2. 插入特殊结点

参考自：Binary Tree Level Order Traversal

通过插入特殊结点，来判断一层是否结束。这样做的好处是不用统计每一层结点数目。伪代码如下：

  1. a queue stores [step0, step1, step2, ...]
  3. queue.add(first step)
  5. while queue is not empty
  7.   current_step = queue.poll()
  9.   // do something here with current_step
  10.   // like counting
  12.   foreah step in current_step can jump to
  13.     queue.add(step)

代码1：通过统计每一行的结点数：

  1.     public List<List<Integer>> levelOrder(TreeNode root) {
  3.         List<List<Integer>> rt = new ArrayList<List<Integer>>();
  5.         if (root == null) {
  6.             return rt;
  7.         }
  9.         Deque<TreeNode> deque = new LinkedList<TreeNode>();
  10.         deque.add(root);
  12.         int toBePrinted = 1;
  13.         int nextLevel = 0;
  15.         List<Integer> level = new LinkedList<Integer>();
  17.         while (!deque.isEmpty()) {
  19.             TreeNode p = deque.poll();
  20.             level.add(p.val);
  21.             toBePrinted--;
  23.             if (p.left != null) {
  24.                 deque.addLast(p.left);
  25.                 nextLevel++;
  26.             }
  28.             if (p.right != null) {
  29.                 deque.addLast(p.right);
  30.                 nextLevel++;
  31.             }
  33.             if (toBePrinted == 0) {
  34.                 toBePrinted = nextLevel;
  35.                 nextLevel = 0;
  36.                 rt.add(new ArrayList<Integer>(level));
  37.                 level.clear();
  38.             }
  40.         }
  42.         return rt;
  43.     }

代码2：插入特殊结点：

  1.     public List<List<Integer>> levelOrder2(TreeNode root) {
  3.         List<List<Integer>> rt = new ArrayList<List<Integer>>();
  5.         if (root == null) {
  6.             return rt;
  7.         }
  9.         final TreeNode END = new TreeNode(0);
  11.         Deque<TreeNode> deque = new LinkedList<TreeNode>();
  12.         List<Integer> level = new LinkedList<Integer>();
  14.         deque.add(root);
  15.         deque.add(END);
  17.         while (!deque.isEmpty()) {
  19.             TreeNode p = deque.pop();
  21.             if (p == END) {
  22.                 rt.add(new ArrayList<Integer>(level));
  23.                 level.clear();
  25.                 if (!deque.isEmpty()) {
  26.                     deque.add(END);
  27.                 }
  28.             } else {
  29.                 level.add(p.val);
  31.                 if (p.left != null) {
  32.                     deque.add(p.left);
  33.                 }
  35.                 if (p.right != null) {
  36.                     deque.add(p.right);
  37.                 }
  38.             }
  39.         }
  41.         return rt;
  42.     }

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,#,#,15,7},

  1.     3
  2.    / \
  3.   9  20
  4.     /  \
  5.    15   7

return its bottom-up level order traversal as:

  1. [
  2.   [15,7],
  3.   [9,20],
  4.   [3]
  5. ]

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

参考：LeetCode 102 Binary Tree Level Order Traversal

只是在返回result前，加入一句话

  1. Collections.reverse(result);
  1.     public List<List<Integer>> levelOrderBottom(TreeNode root) {
  3.         List<List<Integer>> rt = new ArrayList<List<Integer>>();
  5.         if (root == null) {
  6.             return rt;
  7.         }
  9.         final TreeNode END = new TreeNode(0);
  11.         Deque<TreeNode> deque = new LinkedList<TreeNode>();
  12.         List<Integer> level = new LinkedList<Integer>();
  14.         deque.add(root);
  15.         deque.add(END);
  17.         while (!deque.isEmpty()) {
  19.             TreeNode p = deque.pop();
  21.             if (p == END) {
  22.                 rt.add(new ArrayList<Integer>(level));
  23.                 level.clear();
  25.                 if (!deque.isEmpty()) {
  26.                     deque.add(END);
  27.                 }
  28.             } else {
  29.                 level.add(p.val);
  31.                 if (p.left != null) {
  32.                     deque.add(p.left);
  33.                 }
  35.                 if (p.right != null) {
  36.                     deque.add(p.right);
  37.                 }
  38.             }
  39.         }
  41.         Collections.reverse(rt);
  42.         return rt;
  43.     }

Binary Tree Paths

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

For example, given the following binary tree:

  1.    1
  2.  /   \
  3. 2     3
  4.  \
  5.   5

All root-to-leaf paths are:

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

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

  1.     List<String> rt = new ArrayList<String>();
  2.     List<Integer> path = new ArrayList<Integer>();
  4.     public List<String> binaryTreePaths(TreeNode root) {
  5.         findPath(root);
  6.         return rt;
  7.     }
  9.     void findPath(TreeNode root) {
  11.         if (root == null) {
  12.             return;
  13.         }
  15.         path.add(root.val);
  17.         // 是一条路径，将path添加到rt中
  18.         if (root.left == null && root.right == null) {
  19.             StringBuffer sb = new StringBuffer();
  20.             sb.append(path.get(0));
  21.             for (int i = 1; i < path.size(); i++) {
  22.                 sb.append("->" + path.get(i));
  23.             }
  24.             rt.add(sb.toString());
  25.         }
  27.         findPath(root.left);
  28.         findPath(root.right);
  30.         path.remove(path.size() - 1);
  31.     }

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.    1            <---
  2.  /   \
  3. 2     3         <---
  4.  \     \
  5.   5     4       <---

You should return [1, 3, 4].

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

1. 递归求解

二叉树，从右边向左边看。那么除了最右边的一个list1，还会有一个相对于最右边的list稍微靠左边一点的list2，如果list2比list1长，则list2较长的部分也是结果。

举个例子：

  1.    1            <---
  2.  /   \
  3. 2     3         <---
  4.  \     \
  5.   5     4       <---
  6.    \
  7.     6           <---

list1是[1, 3, 4], list2是[1, 2, 5, 6]。list2比list1长，长出的部分是6，也在结果之中。

2. 插入特殊结点

通过插入特殊结点，来判断一层是否结束。这样做的好处是不用统计每一层结点数目。

3. 计数法

定义两个变量，toBePrinted和nextLevel。

toBePrinted：当前待打印结点的数量 
nextLevel：下一层的结点数量

通过Deque来进行统计。

代码1：递归求解

  1.     public List<Integer> rightSideView(TreeNode root) {
  3.         List<Integer> rt = new ArrayList<Integer>();
  5.         if (root == null) {
  6.             return rt;
  7.         }
  9.         rt.add(root.val);
  11.         List<Integer> left = rightSideView(root.left);
  12.         List<Integer> right = rightSideView(root.right);
  14.         rt.addAll(right);
  16.         if (left.size() > right.size()) {
  17.             rt.addAll(left.subList(right.size(), left.size()));
  18.         }
  20.         return rt;
  22.     }

代码2：插入特殊结点

  1.     public List<Integer> rightSideView2(TreeNode root) {
  3.         List<Integer> rt = new ArrayList<Integer>();
  4.         if (root == null) {
  5.             return rt;
  6.         }
  8.         final TreeNode END = new TreeNode(0);
  10.         Deque<TreeNode> deque = new LinkedList<TreeNode>();
  12.         deque.add(root);
  13.         deque.add(END);
  15.         while (!deque.isEmpty()) {
  17.             TreeNode p = deque.pop();
  19.             if (p == END) {
  20.                 if (!deque.isEmpty()) {
  21.                     deque.add(END);
  22.                 }
  23.             } else {
  25.                 // 如果deque的下一个是END，则p是层序的最后一个，加入结果rt
  26.                 if (deque.peek() == END) {
  27.                     rt.add(p.val);
  28.                 }
  30.                 if (p.left != null) {
  31.                     deque.add(p.left);
  32.                 }
  34.                 if (p.right != null) {
  35.                     deque.add(p.right);
  36.                 }
  37.             }
  38.         }
  40.         return rt;
  41.     }

代码3：计数法

  1.     public List<Integer> rightSideView3(TreeNode root) {
  3.         List<Integer> rt = new ArrayList<Integer>();
  5.         if (root == null) {
  6.             return rt;
  7.         }
  9.         Deque<TreeNode> deque = new LinkedList<TreeNode>();
  10.         deque.add(root);
  12.         int toBePrinted = 1;
  13.         int nextLevel = 0;
  15.         List<Integer> level = new LinkedList<Integer>();
  17.         while (!deque.isEmpty()) {
  19.             TreeNode p = deque.poll();
  20.             level.add(p.val);
  21.             toBePrinted--;
  23.             if (p.left != null) {
  24.                 deque.addLast(p.left);
  25.                 nextLevel++;
  26.             }
  28.             if (p.right != null) {
  29.                 deque.addLast(p.right);
  30.                 nextLevel++;
  31.             }
  33.             if (toBePrinted == 0) {
  34.                 toBePrinted = nextLevel;
  35.                 nextLevel = 0;
  36.                 rt.add(p.val);
  37.                 level.clear();
  38.             }
  40.         }
  42.         return rt;
  43.     }

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,#,#,15,7},

  1.     3
  2.    / \
  3.   9  20
  4.     /  \
  5.    15   7

return its zigzag level order traversal as:

  1. [
  2.   [3],
  3.   [20,9],
  4.   [15,7]
  5. ]

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

参考LeetCode 102 Binary Tree Level Order Traversal

只需要加入一个变量，判断行数，翻转list即可。

  1.     public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
  3.         List<List<Integer>> rt = new ArrayList<List<Integer>>();
  5.         if (root == null) {
  6.             return rt;
  7.         }
  9.         final TreeNode END = new TreeNode(0);
  11.         Deque<TreeNode> deque = new LinkedList<TreeNode>();
  12.         List<Integer> level = new LinkedList<Integer>();
  13.         int count = 0;
  15.         deque.add(root);
  16.         deque.add(END);
  18.         while (!deque.isEmpty()) {
  20.             TreeNode p = deque.pop();
  22.             if (p == END) {
  24.                 if (count % 2 == 1) {
  25.                     Collections.reverse(level);
  26.                 }
  28.                 count++;
  30.                 rt.add(new ArrayList<Integer>(level));
  31.                 level.clear();
  33.                 if (!deque.isEmpty()) {
  34.                     deque.add(END);
  35.                 }
  36.             } else {
  37.                 level.add(p.val);
  39.                 if (p.left != null) {
  40.                     deque.add(p.left);
  41.                 }
  43.                 if (p.right != null) {
  44.                     deque.add(p.right);
  45.                 }
  46.             }
  47.         }
  49.         return rt;
  50.     }

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.     int p;
  2.     int[] postorder;
  3.     int[] inorder;
  5.     public TreeNode buildTree(int[] inorder, int[] postorder) {
  7.         this.p = postorder.length - 1;
  8.         this.inorder = inorder;
  9.         this.postorder = postorder;
  11.         return buildTree(0, postorder.length);
  12.     }
  14.     TreeNode buildTree(int start, int end) {
  16.         if (start >= end) {
  17.             return null;
  18.         }
  20.         TreeNode root = new TreeNode(postorder[p]);
  22.         int i;
  23.         for (i = start; i < end && postorder[p] != inorder[i]; i++)
  24.             ;
  26.         p--;
  27.         root.right = buildTree(i + 1, end);
  28.         root.left = buildTree(start, i);
  30.         return root;
  31.     }

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.     int p = 0;
  2.     int[] preorder;
  3.     int[] inorder;
  5.     public TreeNode buildTree(int[] preorder, int[] inorder) {
  7.         this.preorder = preorder;
  8.         this.inorder = inorder;
  10.         return buildTree(0, preorder.length);
  11.     }
  13.     TreeNode buildTree(int start, int end) {
  15.         if (start >= end) {
  16.             return null;
  17.         }
  19.         TreeNode root = new TreeNode(preorder[p]);
  21.         int i;
  22.         for (i = start; i < end && preorder[p] != inorder[i]; i++)
  23.             ;
  25.         p++;
  26.         root.left = buildTree(start, i);
  27.         root.right = buildTree(i + 1, end);
  29.         return root;
  30.     }

Convert Sorted Array to Binary Search Tree

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

参考：LeetCode 105 Construct Binary Tree from Preorder and Inorder Traversal

只是根结点为mid，核心代码如下：

  1.         int mid = (start + end) / 2;
  2.         TreeNode root = new TreeNode(nums[mid]);
  4.         root.left = buildBST(start, mid);
  5.         root.right = buildBST(mid + 1, end);
  1.     int[] nums;
  3.     public TreeNode sortedArrayToBST(int[] nums) {
  5.         this.nums = nums;
  7.         return buildBST(0, nums.length);
  8.     }
  10.     TreeNode buildBST(int start, int end) {
  12.         if (start >= end) {
  13.             return null;
  14.         }
  16.         int mid = (start + end) / 2;
  17.         TreeNode root = new TreeNode(nums[mid]);
  19.         root.left = buildBST(start, mid);
  20.         root.right = buildBST(mid + 1, end);
  22.         return root;
  23.     }
  25.     public TreeNode sortedArrayToBST2(int[] nums) {
  27.         if (nums.length == 0) {
  28.             return null;
  29.         }
  31.         if (nums.length == 1) {
  32.             return new TreeNode(nums[0]);
  33.         }
  35.         int mid = nums.length / 2;
  37.         TreeNode root = new TreeNode(nums[mid]);
  39.         root.left = sortedArrayToBST2(Arrays.copyOfRange(nums, 0, mid));
  40.         root.right = sortedArrayToBST2(Arrays.copyOfRange(nums, mid + 1,
  41.                 nums.length));
  43.         return root;
  44.     }

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.

如果层序遍历，时间复杂度是O(n)。可以使用类似二分查找的方法，因为二叉树是完全二叉树，计算leftHeight和rightHeight，最大相差1，然后递归求解。

  1.     public int countNodes(TreeNode root) {
  3.         if (root == null) {
  4.             return 0;
  5.         }
  7.         int leftHeight = 0;
  8.         int rightHeight = 0;
  10.         // 计算leftHeight
  11.         TreeNode p = root;
  12.         while (p != null) {
  13.             p = p.left;
  14.             leftHeight++;
  15.         }
  17.         // 计算rightHeight
  18.         p = root;
  19.         while (p != null) {
  20.             p = p.right;
  21.             rightHeight++;
  22.         }
  24.         // 如果相等，满足2^n-1
  25.         if (leftHeight == rightHeight) {
  26.             return (1 << leftHeight) - 1;
  27.         }
  29.         return 1 + countNodes(root.left) + countNodes(root.right);
  30.     }

Flatten Binary Tree to Linked List

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

For example,
Given

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

The flattened tree should look like:

  1.    1
  2.     \
  3.      2
  4.       \
  5.        3
  6.         \
  7.          4
  8.           \
  9.            5
  10.             \
  11.              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.     TreeNode prev;
  3.     void preorder(TreeNode root) {
  5.         if (root == null)
  6.             return;
  8.         TreeNode left = root.left;
  9.         TreeNode right = root.right;
  11.         // root
  12.         if (prev != null) {
  13.             prev.right = root;
  14.             prev.left = null;
  15.         }
  17.         prev = root;
  19.         preorder(left);
  20.         preorder(right);
  21.     }
  23.     public void flatten(TreeNode root) {
  24.         prev = null;
  25.         preorder(root);
  26.     }

Invert Binary Tree

Invert a binary tree.

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

to

  1.      4
  2.    /   \
  3.   7     2
  4.  / \   / \
  5. 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 TreeNode invertTree(TreeNode root) {
  3.         if ((root == null) || (root.left == null && root.right == null)) {
  4.             return root;
  5.         }
  7.         TreeNode tmp = root.left;
  8.         root.left = root.right;
  9.         root.right = tmp;
  11.         if (root.left != null) {
  12.             invertTree(root.left);
  13.         }
  15.         if (root.right != null) {
  16.             invertTree(root.right);
  17.         }
  19.         return root;
  20.     }

Kth Smallest Element in a BST

Given a binary search tree, write a function kthSmallest to find the **k**th 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?

Hint:

  1. Try to utilize the property of a BST.
  2. What if you could modify the BST node's structure?
  3. The optimal runtime complexity is O(height of BST).

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

因为是BST，那么中序遍历即得到从小到大的序列。中序遍历，到第k次即可。

  1.     public int kthSmallest(TreeNode root, int k) {
  3.         if (root == null) {
  4.             return -1;
  5.         }
  7.         Stack<TreeNode> stack = new Stack<TreeNode>();
  8.         TreeNode p = root;
  10.         while (p != null || !stack.isEmpty()) {
  12.             while (p != null) {
  13.                 stack.push(p);
  14.                 p = p.left;
  15.             }
  17.             if (!stack.isEmpty()) {
  18.                 p = stack.pop();
  19.                 if (--k == 0) {
  20.                     return p.val;
  21.                 }
  22.                 p = p.right;
  23.             }
  24.         }
  26.         return 0;
  27.     }

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).”

  1.         _______6______
  2.        /              \
  3.     ___2__          ___8__
  4.    /      \        /      \
  5.    0      _4       7       9
  6.          /  \
  7.          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.

BST，性质是：根结点都比左结点大，比右结点小。所以给定两个结点，找公共祖先，就是找值在两个结点间的结点。

  1.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  3.         if (root == null || p == null || q == null) {
  4.             return null;
  5.         }
  7.         int m = Math.min(p.val, q.val);
  8.         int n = Math.max(p.val, q.val);
  10.         while (root != null) {
  11.             if (root.val < m) {
  12.                 root = root.right;
  13.             } else if (root.val > n) {
  14.                 root = root.left;
  15.             } else {
  16.                 return root;
  17.             }
  18.         }
  20.         return null;
  21.     }

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).”

  1.         _______3______
  2.        /              \
  3.     ___5__          ___1__
  4.    /      \        /      \
  5.    6      _2       0       8
  6.          /  \
  7.          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.

传统的解法是：从根结点开始，分别记录从根结点到指定结点的路径path1和path2，再比较path1和path2最后一个相同的结点。

http://www.fusu.us/2013/06/p2-lowest-common-ancestor-in-binary-tree.html

这个网址给出了一个更简洁、高效的解法。主要思路是：

  1. 从叶结点开始，向上搜索

  2. 对于每一个结点node 

    • l：node的左子树是否出现过p或q
    • r：node的右子树是否出现过p或q
  3. 如果l和r都不是null，则该结点即为lca

说明，对于一个结点node，l和r只可能有4种情况：

  1. l=null, r=null：node不含有p和q中的任意一个
  2. l!=null, r=null：node左子树含有其中一个
  3. l=null, r!=null：node右子树含有其中一个
  4. l!=null, r!=null：node左、右子树各有其中一个（由于是从叶节点向根结点搜索，所以最先出现该情况的结点，必为lca）

有没有可能，p是q的祖先？没有影响，因为如果是自身的话，也算包含在左右子树中。

  1.         -1
  2.        /  \
  3.       0    3
  4.      / \
  5.    -2   4
  6.    /
  7.   8

具体分析：寻找结点值为8和4的lca

  1. 首先进入结点-1，0，-2
  2. 在结点-2时，-2的左结点是8，是其中一个结点，则l置为8，不为空。-2的右结点是null，r仍然是null。表面-2不是lca
  3. 进入结点0，此时l已经不是null，0的右结点是4，是其中一个结点，则r置为4，不为空。
  4. 此时，l和r都不为null，0就是lca
  1.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  3.         // 发现目标结点，则标记（left或right）
  4.         if (root == null || root == p || root == q)
  5.             return root;
  7.         // 查看左右子树是否有目标结点
  8.         TreeNode left = lowestCommonAncestor(root.left, p, q);
  9.         TreeNode right = lowestCommonAncestor(root.right, p, q);
  11.         // 左右子树同时含有目标结点，则该结点是lca
  12.         if (left != null && right != null)
  13.             return root;
  15.         // 左右子树只有一个含有目标结点，向上返回
  16.         return left == null ? right : left;
  17.     }

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.     public int maxDepth(TreeNode root) {
  3.         if (root == null) {
  4.             return 0;
  5.         }
  7.         int nLeft = maxDepth(root.left);
  8.         int nRight = maxDepth(root.right);
  10.         return nLeft > nRight ? (nLeft + 1) : (nRight + 1);
  11.     }

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.

参考：LeetCode 104 Maximum Depth of Binary Tree

Minimum Depth的定义如下：

这里写图片描述

  1.     public int minDepth(TreeNode root) {
  3.         if (root == null) {
  4.             return 0;
  5.         }
  7.         if (root.left == null && root.right == null) {
  8.             return 1;
  9.         } else if (root.left != null && root.right == null) {
  10.             return minDepth(root.left) + 1;
  11.         } else if (root.left == null && root.right != null) {
  12.             return minDepth(root.right) + 1;
  13.         }
  15.         return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
  16.     }

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,

  1.               5
  2.              / \
  3.             4   8
  4.            /   / \
  5.           11  13  4
  6.          /  \      \
  7.         7    2      1

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

  1.     boolean hasPath;
  3.     public boolean hasPathSum(TreeNode root, int sum) {
  5.         if (root == null) {
  6.             return false;
  7.         }
  9.         hasPath = false;
  10.         help(root, 0, sum);
  11.         return hasPath;
  12.     }
  14.     void help(TreeNode node, int cur, int sum) {
  16.         cur += node.val;
  18.         boolean isLeaf = (node.left == null) && (node.right == null);
  20.         if (cur == sum && isLeaf) {
  21.             hasPath = true;
  22.         }
  24.         if (node.left != null) {
  25.             help(node.left, cur, sum);
  26.         }
  28.         if (node.right != null) {
  29.             help(node.right, cur, sum);
  30.         }
  32.         cur -= node.val;
  33.     }

更简洁的做法：

  1.     public boolean hasPathSum2(TreeNode root, int sum) {
  3.         if (root == null) {
  4.             return false;
  5.         }
  7.         if (root.left == null && root.right == null) {
  8.             return root.val == sum;
  9.         }
  11.         return (root.left != null && hasPathSum2(root.left, sum - root.val))
  12.                 || (root.right != null && hasPathSum2(root.right, sum
  13.                         - root.val));
  14.     }

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,

  1.               5
  2.              / \
  3.             4   8
  4.            /   / \
  5.           11  13  4
  6.          /  \    / \
  7.         7    2  5   1

return

  1. [
  2.    [5,4,11,2],
  3.    [5,8,4,5]
  4. ]

参考：LeetCode 112 Path Sum

只不过记录了路径。

  1.     List<List<Integer>> result;
  2.     List<Integer> path;
  3.     int sum;
  5.     public List<List<Integer>> pathSum(TreeNode root, int sum) {
  7.         result = new ArrayList<List<Integer>>();
  8.         path = new ArrayList<Integer>();
  9.         this.sum = sum;
  11.         if (root == null) {
  12.             return result;
  13.         }
  15.         help(root, 0);
  17.         return result;
  18.     }
  20.     void help(TreeNode node, int cur) {
  22.         cur += node.val;
  23.         path.add(node.val);
  25.         boolean isLeaf = (node.left == null) && (node.right == null);
  27.         if (cur == sum && isLeaf) {
  28.             result.add(new ArrayList<Integer>(path));
  29.         }
  31.         if (node.left != null) {
  32.             help(node.left, cur);
  33.         }
  35.         if (node.right != null) {
  36.             help(node.right, cur);
  37.         }
  39.         cur -= node.val;
  40.         path.remove(path.size() - 1);
  41.     }

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:

For example,
Given the following perfect binary tree,

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

After calling your function, the tree should look like:

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

本来使用迭代的方法，利用deque去做。但是不如递归简洁。

  1.     public class TreeLinkNode {
  2.         int val;
  3.         TreeLinkNode left, right, next;
  5.         TreeLinkNode(int x) {
  6.             val = x;
  7.         }
  8.     }
  10.     public void connect(TreeLinkNode root) {
  12.         if (root == null) {
  13.             return;
  14.         }
  16.         if (root.left != null && root.right != null) {
  17.             root.left.next = root.right;
  18.         }
  20.         if (root.next != null && root.next.left != null) {
  21.             root.right.next = root.next.left;
  22.         }
  24.         connect(root.left);
  25.         connect(root.right);
  26.     }

Same Tree

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

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

  1.     public boolean isSameTree(TreeNode p, TreeNode q) {
  3.         if (p == null && q == null) {
  4.             return true;
  5.         } else if (p == null || q == null) {
  6.             return false;
  7.         }
  9.         return p.val == q.val && isSameTree(p.left, q.left)
  10.                 && isSameTree(p.right, q.right);
  11.     }

Symmetric Tree

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

For example, this binary tree is symmetric:

  1.     1
  2.    / \
  3.   2   2
  4.  / \ / \
  5. 3  4 4  3

But the following is not:

  1.     1
  2.    / \
  3.   2   2
  4.    \   \
  5.    3    3

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

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

递归

参考LeetCode 100 Same Tree，仅仅将判断条件改成p.left和q.right、p.right和q.left相比即可。

  1.     // recursively
  2.     public boolean isSymmetric(TreeNode root) {
  4.         if (root == null) {
  5.             return true;
  6.         }
  8.         return isSymmetric(root.left, root.right);
  9.     }
  11.     boolean isSymmetric(TreeNode p, TreeNode q) {
  13.         if (p == null && q == null) {
  14.             return true;
  15.         } else if (p == null || q == null) {
  16.             return false;
  17.         }
  19.         return p.val == q.val && isSymmetric(p.left, q.right)
  20.                 && isSymmetric(p.right, q.left);
  21.     }

迭代

考虑用队列，每次add两个对应的结点。

如果队列长度为0，则退出循环；否则取出队列中的两个结点，对值进行判断。

  1.     // iteratively
  2.     public boolean isSymmetric2(TreeNode root) {
  4.         if (root == null) {
  5.             return true;
  6.         }
  8.         Deque<TreeNode> deque = new LinkedList<TreeNode>();
  10.         if (root.left == null && root.right == null) {
  11.             return true;
  12.         } else if (root.left == null || root.right == null) {
  13.             return false;
  14.         } else {
  15.             deque.addLast(root.left);
  16.             deque.addLast(root.right);
  17.         }
  19.         while (deque.size() != 0) {
  20.             TreeNode p = deque.pop();
  21.             TreeNode q = deque.pop();
  23.             if (p.val != q.val) {
  24.                 return false;
  25.             }
  27.             if (p.left == null && q.right == null) {
  28.                 // do nothing
  29.             } else if (p.left == null || q.right == null) {
  30.                 return false;
  31.             } else {
  32.                 deque.addLast(p.left);
  33.                 deque.addLast(q.right);
  34.             }
  36.             if (p.right == null && q.left == null) {
  37.                 // do nothing
  38.             } else if (p.right == null || q.left == null) {
  39.                 return false;
  40.             } else {
  41.                 deque.addLast(p.right);
  42.                 deque.addLast(q.left);
  43.             }
  44.         }
  46.         return true;
  47.     }

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.     1
  2.    / \
  3.   2   3
  4.      / \
  5.     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.

我的最开始的思路是：先求树的深度h，把树中的每个结点（2^h-1）个结点，全部记录下来，即使是null。但是这样有些极端的测试用例会超时，比如树中每个结点只有右结点，树高1000。用这种方法要遍历2^h-1次，显然能够优化。

参考 how LeetCode OJ serializes a binary tree的序列化方式，下面的二叉树，序列化后的String可以是”1,2,3,null,null,4,null,5,null”，这种方法在序列化二叉树时，只用树结点数量规模的字符即可，省时省空间。

  1.     1
  2.    / \
  3.   2   3
  4.      / 
  5.     4   
  6.    /
  7.   5
  1.     public String serialize(TreeNode root) {
  3.         if (root == null) {
  4.             return "";
  5.         }
  7.         StringBuffer sb = new StringBuffer();
  9.         Deque<TreeNode> deque = new LinkedList<TreeNode>();
  10.         deque.add(root);
  12.         while (!deque.isEmpty()) {
  13.             TreeNode p = deque.pop();
  15.             if (p == null) {
  16.                 sb.append(",#");
  17.             } else {
  18.                 sb.append("," + p.val);
  19.                 deque.add(p.left);
  20.                 deque.add(p.right);
  21.             }
  22.         }
  24.         // 第一个元素前也有一个逗号，截取
  25.         return sb.toString().substring(1);
  26.     }
  28.     public TreeNode deserialize(String data) {
  30.         if (data == null || data.length() == 0) {
  31.             return null;
  32.         }
  34.         String[] s = data.split(",");
  36.         TreeNode[] node = new TreeNode[s.length];
  38.         // 新建TreeNode，并初始化
  39.         for (int i = 0; i < node.length; i++) {
  40.             if (!"#".equals(s[i])) {
  41.                 node[i] = new TreeNode(Integer.valueOf(s[i]));
  42.             }
  43.         }
  45.         int parent = 0;
  47.         // 将结点连接起来
  48.         for (int i = 0; parent * 2 + 2 < s.length; i++) {
  49.             if (node[i] != null) {
  50.                 node[i].left = node[parent * 2 + 1];
  51.                 node[i].right = node[parent * 2 + 2];
  52.                 parent++;
  53.             }
  54.         }
  56.         return node[0];
  57.     }

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.     1
  2.    / \
  3.   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.

参考：Sum Root to Leaf Numbers

这里写图片描述

  1.     int sumNumbers(TreeNode root, int parentval) {
  3.         if (root == null) {
  4.             return 0;
  5.         }
  7.         int p = parentval * 10 + root.val;
  9.         if (root.left == null && root.right == null) {
  10.             return p;
  11.         }
  13.         return sumNumbers(root.left, p) + sumNumbers(root.right, p);
  14.     }

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.    1         3     3      2      1
  2.     \       /     /      / \      \
  3.      3     2     1      1   3      2
  4.     /     /       \                 \
  5.    2     1         2                 3
  1. 以n为根结点的二叉树个数=左子树个数*右子树个数
  2. 用数组record[n+1]记录以0~n的情况，自底向上，否则会超时
  1.     public int numTrees(int n) {
  3.         if (n == 1 || n == 2) {
  4.             return n;
  5.         }
  7.         // record[0]没有用，所以长度是n+1
  8.         // 使用数组，从下向上保存结果，能够节省时间，否则会超时
  9.         int[] record = new int[n + 1];
  11.         record[0] = 1;
  12.         record[1] = 1; // 1个元素时，情况为1
  13.         record[2] = 2; // 2个元素时，情况为2
  15.         for (int i = 3; i <= n; i++) {
  16.             int tmp = 0;
  17.             for (int k = 0; k < i; k++) {
  18.                 // 以n为根结点的二叉树个数=左结点的二叉树个数*右结点的二叉树个数
  19.                 // 题目所求要包括所有情况，分别以1~n为根结点
  20.                 tmp += (record[k] * record[i - k - 1]);
  21.             }
  22.             // 记录1~i时，BST的个数
  23.             record[i] = tmp;
  24.         }
  26.         return record[n];
  27.     }

Unique Binary Search Trees II

Given 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.    1         3     3      2      1
  2.     \       /     /      / \      \
  3.      3     2     1      1   3      2
  4.     /     /       \                 \
  5.    2     1         2                 3

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

  1.     public List<TreeNode> generateTrees(int n) {
  3.         int[] array = new int[n];
  5.         // 建立1~n的数组
  6.         for (int i = 0; i < n; i++) {
  7.             array[i] = i + 1;
  8.         }
  10.         return generateTrees(array);
  11.     }
  13.     List<TreeNode> generateTrees(int[] array) {
  15.         if (array.length == 0) {
  16.             return new ArrayList<TreeNode>(
  17.                     Collections.<TreeNode> singletonList(null));
  18.         }
  20.         ArrayList<TreeNode> rt = new ArrayList<TreeNode>();
  22.         // 数组的每一个元素（array[i]），分别作为根结点
  23.         for (int i = 0; i < array.length; i++) {
  24.             // array[i]作为根结点，array[i]之前的元素为左结点，array[i]之后的元素为右结点
  25.             for (TreeNode left : generateTrees(Arrays.copyOfRange(array, 0, i))) {
  26.                 for (TreeNode right : generateTrees(Arrays.copyOfRange(array,
  27.                         i + 1, array.length))) {
  28.                     TreeNode root = new TreeNode(array[i]);
  30.                     root.left = left;
  31.                     root.right = right;
  33.                     rt.add(root);
  34.                 }
  35.             }
  36.         }
  38.         return rt;
  39.     }

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:

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

验证一棵树是否为BST，只需要验证中序遍历序列是否是递增的。

  1.     boolean failed = false;
  3.     // 要用long，而不是int
  4.     // 否则涉及到Integer.MIN_VALUE的用例会出现错误
  5.     // 比如{Integer.MIN_VALUE}这个用例会错误
  6.     long last = Long.MIN_VALUE;
  8.     public boolean isValidBST(TreeNode root) {
  10.         if (root == null) {
  11.             return true;
  12.         }
  14.         inorder(root);
  15.         return !failed;
  16.     }
  18.     private void inorder(TreeNode root) {
  20.         if (root == null || failed) {
  21.             return;
  22.         }
  24.         // 左
  25.         inorder(root.left);
  27.         // 中，相当于中序遍历中的打印操作
  28.         // 只采用了一个变量，所以空间复杂度是O(1)
  29.         // 传统的做法是建立一个ArrayList，然后判断中序遍历是否是递增的，但是空间复杂度是O(n)
  30.         if (last >= root.val) {
  31.             failed = true;
  32.         }
  33.         last = root.val;
  35.         // 右
  36.         inorder(root.right);
  37.     }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注