Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.
Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longestpath between any two nodes in a tree. This path may or may not pass through the root.
Example: Given a binary tree
1 2 3 4 5 6
1 / \ 2 3 / \ 4 5
Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].
Note: The length of path between two nodes is represented by the number of edges between them.
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 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
classSolution { public: boolisBalanced(TreeNode* root){ if(!root) returntrue; returndfsHeight(root) != -1; } intdfsHeight(TreeNode* root){ if(!root) return0; int l = dfsHeight(root->left); if(l==-1) return-1; int r = dfsHeight(root->right); if(r==-1) return-1; if(abs(l-r)>1) return-1; return1+max(dfsHeight(root->left), dfsHeight(root->right)); } };
111. Minimum Depth of Binary Tree
Description:
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.
classSolution { private: vector<int> res; public: vector<int> findMode(TreeNode* root){ int max, pre, cnt; getMax(root, max=0, pre, cnt=0); getMode(root, max, pre, cnt=0); return res; } voidgetMax(TreeNode* root, int &max, int &pre, int &cnt){ if(!root) return; getMax(root->left, max, pre, cnt); getMax(root->right, max=cnt>max?cnt:max, pre=root->val, ++(cnt*=(pre==root->val))); } voidgetMode(TreeNode* root, int max, int &pre, int &cnt){ if(!root) return; getMode(root->left, max, pre, cnt); if(++(cnt*=(root->val==pre)) == max) res.push_back(root->val); getMode(root->right, max, pre=root->val, cnt); } };
538. Convert BST to Greater Tree
Description:
Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST.
Example:
1 2 3 4 5 6 7 8 9
Input: The root of a Binary Search Tree like this: 5 / \ 2 13
Output: The root of a Greater Tree like this: 18 / \ 20 13
Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not.
You need to merge them into a new binary tree. The merge rule is that if two nodes overlap, then sum node values up as the new value of the merged node. Otherwise, the NOT null node will be used as the node of new tree.
Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.
Example 1:
1 2 3 4 5 6 7 8 9 10
Input: 3 / \ 9 20 / \ 15 7 Output: [3, 14.5, 11] Explanation: The average value of nodes on level 0 is 3, on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11].
Note:
The range of node’s value is in the range of 32-bit signed integer.
235. Lowest Common Ancestor of a Binary Search Tree
Description:
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).”
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.
Given a binary tree, return the tilt of the whole tree.
The tilt of a tree node is defined as the absolute difference between the sum of all left subtree node values and the sum of all right subtree node values. Null node has tilt 0.
The tilt of the whole tree is defined as the sum of all nodes’ tilt.
Example:
1 2 3 4 5 6 7 8 9 10 11
Input: 1 / \ 2 3 Output: 1 Explanation: Tilt of node 2 : 0 Tilt of node 3 : 0 Tilt of node 1 : |2-3| = 1 Tilt of binary tree : 0 + 0 + 1 = 1
Note:
The sum of node values in any subtree won’t exceed the range of 32-bit integer.
All the tilt values won’t exceed the range of 32-bit integer.
解题思路：代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
classSolution { public: int result = 0; intfindTilt(TreeNode* root){ postOrder(root); return result; } intpostOrder(TreeNode* root){ if(!root) return0; int l = postOrder(root->left); int r = postOrder(root->right); result += abs(l-r); return l+r+root->val; } };
572. Subtree of Another Tree
Description:
Given two non-empty binary trees s and t, check whether tree t has exactly the same structure and node values with a subtree of s. A subtree of s is a tree consists of a node in s and all of this node’s descendants. The tree s could also be considered as a subtree of itself.
Given a non-empty special binary tree consisting of nodes with the non-negative value, where each node in this tree has exactly two or zero sub-node. If the node has two sub-nodes, then this node’s value is the smaller value among its two sub-nodes.
Given such a binary tree, you need to output the second minimum value in the set made of all the nodes’ value in the whole tree.
If no such second minimum value exists, output -1 instead.
Example 1:
1 2 3 4 5 6 7 8 9 10
Input: 2 / \ 2 5 / \ 5 7
Output: 5 Explanation: The smallest value is 2, the second smallest value is 5.
Example 2:
1 2 3 4 5 6 7
Input: 2 / \ 2 2
Output: -1 Explanation: The smallest value is 2, but there isn't any second smallest value.
classSolution { public: intfindSecondMinimumValue(TreeNode* root){ if(root->left){ if(root->left->val < root->right->val){ int l = findSecondMinimumValue(root->left); if(l==-1) return root->right->val; returnmin(l, root->right->val); }elseif(root->left->val > root->right->val){ int r = findSecondMinimumValue(root->right); if(r==-1) return root->left->val; returnmin(r, root->left->val); }else{ int l = findSecondMinimumValue(root->left); int r = findSecondMinimumValue(root->right); if(l==-1) return r; if(r==-1) return l; returnmin(l, r); } }else{ return-1; } return-1; } };
687. Longest Univalue Path
Description:
Given a binary tree, find the length of the longest path where each node in the path has the same value. This path may or may not pass through the root.
Note: The length of path between two nodes is represented by the number of edges between them.
Example 1:
Input:
1 2 3 4 5 6
5 / \ 4 5 / \ \ 1 1 5
Output:
1 2
2
Example 2:
Input:
1 2 3 4 5 6
1 / \ 4 5 / \ \ 4 4 5
Output:
1 2
2
Note: The given binary tree has not more than 10000 nodes. The height of the tree is not more than 1000.
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],
#include<stdio.h> /** Definition for binary tree with next pointer.*/ structTreeLinkNode { int val; TreeLinkNode *left, *right, *next; TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {} }; classSolution { public: voidconnect(TreeLinkNode *root){ TreeLinkNode* head = NULL; //head of the next level TreeLinkNode* prev = NULL; //the leading node on the next level TreeLinkNode* cur = root; //current node of current level while (cur != NULL) { while (cur != NULL) { //iterate on the current level //left child if (cur->left != NULL) { if (prev != NULL) { prev->next = cur->left; } else { head = cur->left; } prev = cur->left; } //right child if (cur->right != NULL) { if (prev != NULL) { prev->next = cur->right; } else { head = cur->right; } prev = cur->right; } //move to next node cur = cur->next; } //move to next level cur = head; head = NULL; prev = NULL; } } };
124. Binary Tree Maximum Path Sum
Description:
Given a non-empty 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.
#include<stdio.h> #include<stdlib.h> #include<limits.h> #include<algorithm> usingnamespace std; /** * Definition for a binary tree node.*/ structTreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; classSolution { private: int maxVal; public: intmaxPathSum(TreeNode* root){ maxVal=INT_MIN; maxPathSumDown(root); return maxVal; } intmaxPathSumDown(TreeNode* node){ if(node==NULL) return0; int left=max(0,maxPathSumDown(node->left)); int right=max(0,maxPathSumDown(node->right)); maxVal=max(maxVal,left+right+node->val); returnmax(left,right)+node->val; } };
129. 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.
Note: A leaf is a node with no children.
Example:
1 2 3 4 5 6 7 8 9
Input: [1,2,3] 1 / \ 2 3 Output: 25 Explanation: The root-to-leaf path 1->2 represents the number 12. The root-to-leaf path 1->3 represents the number 13. Therefore, sum = 12 + 13 = 25.
Example 2:
1 2 3 4 5 6 7 8 9 10 11 12
Input: [4,9,0,5,1] 4 / \ 9 0 / \ 5 1 Output: 1026 Explanation: The root-to-leaf path 4->9->5 represents the number 495. The root-to-leaf path 4->9->1 represents the number 491. The root-to-leaf path 4->0 represents the number 40. Therefore, sum = 495 + 491 + 40 = 1026.
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]
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Output: 3 Explanation: The LCA of of nodes 5 and 1 is 3.
Example 2:
1 2 3 4
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 Output: 5 Explanation: The LCA of nodes 5 and 4 is 5, 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.