Binary tree is one of the most frequently asked question type during interview.
二叉树是面试中经常会问到的问题。
The candidate needs to understand the recursively defined TreeNode and solve the problem through recursion.
面试者需要理解递归定义的TreeNode数据类型，并且通过使用递归的方式来解决问题。
Posts tagged as “tree”
Problem
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.
Note: A leaf is a node with no children.
Example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its minimum depth = 2.
Solution: Recursion
Time complexity: O(n)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 |
// Author: Huahua, 4 ms class Solution { public: int minDepth(TreeNode* root) { if (!root) return 0; if (!root->left && !root->right) return 1; int l = root->left ? minDepth(root->left) : INT_MAX; int r = root->right ? minDepth(root->right) : INT_MAX; return min(l, r) + 1; } }; |
Python3
|
1 2 3 4 5 6 7 8 9 |
class Solution: def minDepth(self, root): if not root: return 0 if not root.left and not root.right: return 1 l = self.minDepth(root.left) r = self.minDepth(root.right) if not root.left: return 1 + r if not root.right: return 1 + l return 1 + min(l, r) |
Related Problem
Problem
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.
Note: A leaf is a node with no children.
Example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its depth = 3.
Solution: Recursion
maxDepth(root) = max(maxDepth(root.left), maxDepth(root.right)) + 1
Time complexity: O(n)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 |
// Author: Huahua, 4 ms class Solution { public: int maxDepth(TreeNode* root) { if (!root) return 0; int l = maxDepth(root->left); int r = maxDepth(root->right); return max(l, r) + 1; } }; |
Python3
|
1 2 3 4 5 6 7 |
# Author: Huahua, 80 ms class Solution: def maxDepth(self, root): if not root: return 0 l = self.maxDepth(root.left) r = self.maxDepth(root.right) return max(l, r) + 1 |
Problem
A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
Write a data structure CBTInserter that is initialized with a complete binary tree and supports the following operations:
CBTInserter(TreeNode root)initializes the data structure on a given tree with head noderoot;CBTInserter.insert(int v)will insert aTreeNodeinto the tree with valuenode.val = vso that the tree remains complete, and returns the value of the parent of the insertedTreeNode;CBTInserter.get_root()will return the head node of the tree.
Example 1:
Input: inputs = ["CBTInserter","insert","get_root"], inputs = [[[1]],[2],[]] Output: [null,1,[1,2]]
Example 2:
Input: inputs = ["CBTInserter","insert","insert","get_root"], inputs = [[[1,2,3,4,5,6]],[7],[8],[]] Output: [null,3,4,[1,2,3,4,5,6,7,8]]
Note:
- The initial given tree is complete and contains between
1and1000nodes. CBTInserter.insertis called at most10000times per test case.- Every value of a given or inserted node is between
0and5000.
Solution 2: Deque
Using a deck to keep track of insertable nodes (potential parents) in order.
Time complexity: O(1) / O(n) first call
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
// Author: Huahua class CBTInserter { public: CBTInserter(TreeNode* root): root_(root), d_({root}) {} int insert(int v) { while (!d_.empty()) { TreeNode* r = d_.front(); if (r->left && r->right) { d_.push_back(r->left); d_.push_back(r->right); d_.pop_front(); } else if (r->left) { r->right = new TreeNode(v); return r->val; } else { r->left = new TreeNode(v); return r->val; } } } TreeNode* get_root() { return root_; } private: std::deque<TreeNode*> d_; TreeNode* root_; }; |
Problem
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 p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Given the following binary tree: root = [3,5,1,6,2,0,8,null,null,7,4]
_______3______
/ \
___5__ ___1__
/ \ / \
6 _2 0 8
/ \
7 4
Example 1:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Output: 3 Explanation: The LCA of of nodes5and1is3.
Example 2:
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 Output: 5 Explanation: The LCA of nodes5and4is5, since a node can be a descendant of itself according to the LCA definition.
Note:
- All of the nodes’ values will be unique.
- p and q are different and both values will exist in the binary tree.
Solution 1: Recursion
Time complexity: O(n)
Space complexity: O(h)
For a given root, recursively call LCA(root.left, p, q) and LCA(root.right, p, q)
if both returns a valid node which means p, q are in different subtrees, then root will be their LCA.
if only one valid node returns, which means p, q are in the same subtree, return that valid node as their LCA.
C++
|
1 2 3 4 5 6 7 8 9 10 11 |
// Author: Huahua class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { if (!root || root == p || root == q) return root; TreeNode* l = lowestCommonAncestor(root->left, p, q); TreeNode* r = lowestCommonAncestor(root->right, p, q); if (l && r) return root; return l ? l : r; } }; |
Java
|
1 2 3 4 5 6 7 8 9 10 |
// Author: Huahua class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if (root == null || root == p || root == q) return root; TreeNode l = lowestCommonAncestor(root.left, p, q); TreeNode r = lowestCommonAncestor(root.right, p, q); if (l == null || r == null) return l == null ? r : l; return root; } } |
Python3
|
1 2 3 4 5 6 7 8 |
# Author: Huahua class Solution: def lowestCommonAncestor(self, root, p, q): if any((not root, root == p, root == q)): return root l = self.lowestCommonAncestor(root.left, p, q) r = self.lowestCommonAncestor(root.right, p, q) if not l or not r: return l if l else r return root |