LeetCode-tree类总结（会持续更新...）

算法 评论

本文主要是对leetcode中的tree类算法的总结，包含了各题的solution和常用的解决方法。

相关源码：code

此类题的常用思路：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
1. 树的遍历
2. 递归
3. 树的搜索
4. 集合数据结构
5. BST的中序遍历
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

107. Binary Tree Level Order Traversal II

Description:

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],

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

return its bottom-up level order traversal as:

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

解题思路：本题要求按层打印并且自底向上，故需要使用队列和栈 ，代码如下：

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
class Solution {
public:
    vector<vector<int>> levelOrderBottom(TreeNode* root) {
        vector<vector<int>> res;
      	queue<TreeNode*> q;
      	stack<vector<int>> tower;
      	if(root) q.push(root);
      	while(!q.empty()){
            vector<int> temp;
          	size = q.size();
          	for(int i=0; i<size; i++){
                TreeNode* node = q.front();
              	q.pop();
              	if(node->left) q.push(node->left);
              	if(node->right) q.push(node->right);
              	temp.push_back(root->val);
            }
          	tower.push(temp);
        }
      	while(!tower.empty()){
            res.push_back(tower.top());
          	tower.pop();
        }
      	return res;
    }
};

404. Sum of Left Leaves

Description:

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

Example:

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

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

解题思路：使用递归，代码如下：

1
2
3
4
5
6
7
8
class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if(!root) return 0;
      	if(root->left && root->left->left==NULL && root->left->right == NULL) return root->left->val + sumOfLeftLeaves(root->right);
      	return sumOfLeftLeaves(root->left)+sumOfLeftLeaves(root->right);
    }
};

669. Trim a Binary Search Tree

Description:

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.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
Input: 
    1
   / \
  0   2

  L = 1
  R = 2

Output: 
    1
      \
       2

Example 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
Input: 
    3
   / \
  0   4
   \
    2
   /
  1

  L = 1
  R = 3

Output: 
      3
     / 
   2   
  /
 1

解题思路：本题是BST，所以要用好BST特性。本质上本题考察的是BST的遍历，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution{
public:
    TreeNode* trimBST(TreeNode* root, int L, int R){
        if(!root) return NULL;
        if(root->val < L){
            root = trimBST(root->right, L, R);
        }else if(root->val > R){
            root = trimBST(root->left, L, R);
        }else{
            root->left = trimBST(root->left, L, R);
            root->left = trimBST(root->right, L, R);
        }
        return root;
    }
};

543. Diameter of Binary Tree

Description:

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.

解题思路：属于求树高的变体，思路是使用递归方式遍历，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int diameterOfBinaryTree(TreeNode* root) {
        if(!root) return 0;
        int res = depth(root->left) + depth(root->right);
        return max(res, max(diameterOfBinaryTree(root->left), diameterOfBinaryTree(root->right)));
    }
    
    int depth(TreeNode* root){
        if(!root) return 0;
        return 1+max(depth(root->left), depth(root->right));
    }
};

437. Path Sum III

Description:

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int pathSum(TreeNode* root, int sum) {
        if(!root) return 0;
        return pathSumFrom(root, sum) + pathSum(root->left,sum) + pathSum(root->right,sum);
    }
    
    int pathSumFrom(TreeNode* root, int sum){
        if(!root) return 0;
        return (root->val==sum ? 1 : 0) + pathSumFrom(root->left, sum - root->val) + pathSumFrom(root->right,sum-root->val);
    }
};

110. Balance Binary Tree

Description:

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
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(!root) return true;
      	return dfsHeight(root) != -1;
    }
  
  	int dfsHeight(TreeNode* root){
        if(!root) return 0;
      	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;
      	return 1+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.

解题思路：本题是求深度的变形，重点区分含有双子节点的父节点和含有单子节点的父节点，代码如下：

1
2
3
4
5
6
7
class Solution {
public:
    int minDepth(TreeNode* root) {
        if(!root) return 0;
        return root->left == NULL || root->right == NULL ? 1+max(minDepth(root->left), minDepth(root->right)) : 1+min(minDepth(root->left), minDepth(root->right));
    }
};

112. Path Sum

Description:

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 

1
sum = 22

,

1
2
3
4
5
6
7
8
      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
2
3
4
5
6
7
8
class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(!root) return false;
        if(root->val == sum && root->left == NULL && root->right==NULL) return true;
        return hasPathSum(root->left, sum-root->val) || hasPathSum(root->right, sum - root->val);
    }
};

501. Find Mode in Binary Search Tree

Description:

Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurred element) in the given BST.

Assume a BST is defined as follows:

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

For example:
Given BST [1,null,2,2],

1
2
3
4
5
1
 \
  2
 /
2

return [2].

Note: If a tree has more than one mode, you can return them in any order.

Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
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;
    }
    
    void getMax(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)));
    }
    
    void getMode(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

解题思路：本题考察BST的中序遍历，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
private:
    int sum=0;
public:
    TreeNode* convertBST(TreeNode* root) {
        travel(root);
        return root;
    }
    void travel(TreeNode* root){
        if(root == NULL) return;
        travel(root->right);
        sum += root->val;
        root->val = sum;
        travel(root->left);
    }
};

617. Merge Two Binary Trees

Description:

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.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Input: 
	Tree 1                     Tree 2                  
          1                         2                             
         / \                       / \                            
        3   2                     1   3                        
       /                           \   \                      
      5                             4   7                  
Output: 
Merged tree:
	     3
	    / \
	   4   5
	  / \   \ 
	 5   4   7

Note: The merging process must start from the root nodes of both trees.

解题思路：根据题意来，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
        if(t1!=NULL && t2!=NULL){
            t1->val += t2->val;
        }else if(t1==NULL){
            return t2;
        }else if(t2==NULL){
            return t1;
        }else{
            return NULL;
        }
        t1->left = mergeTrees(t1->left,t2->left);
        t1->right = mergeTrees(t1->right,t2->right);
        return t1;
    }
};

637. Average of Levels in Binary Tree

Description:

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:

  1. The range of node’s value is in the range of 32-bit signed integer.

解题思路：对树进行分层操作，自然而然会想到使用集合数据结构：队列 ，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<double> averageOfLevels(TreeNode* root) {
        vector<double> res;
      	queue<TreeNode*> q;
      	if(root) q.push(root);
      	while(!q.empty()){
            int s = q.size();
          	int temp = 0;
          	for(int i=0; i<s; i++){
                TreeNode* node = q.front();
              	if(node->left) q.push(node->left);
              	if(node->right) q.push(node->right);
              	temp += node->val;
              	q.pop();
            }
          	res.push_back(temp/(double)s);
        }
      	return res;
    }
};

108. Convert Sorted Array to Binary Search Tree

Description:

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

解题思路：根据BST特点解题，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if(nums.size()==0) return NULL;
      	if(nums.size()==1) return new TreeNode(nums[0]);
      	int mid = nums.size()/2;
      	TreeNode* root = new TreeNode(nums[mid]);
      	vector<int> l(nums.begin(), nums.begin()+mid);
      	vector<int> r(nums.begin()+mid+1,nums.end());
      	root->left = sortedArrayToBST(l);
      	root->right = sortedArrayToBST(r);
      	return root;
    }
};

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

1
2
3
4
5
6
7
8
     _______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.

解题思路：结合BST特点，代码如下：

1
2
3
4
5
6
7
8
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root->val < min(p->val, q->val)) return lowestCommonAncestor(root->right, p, q);
        if(root->val > max(p->val, q->val)) return lowestCommonAncestor(root->left, p, q);
        return root;
    }
};

653. Two Sum IV - Input is a BST

Description:

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
Input: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 9

Output: True

Example 2:

1
2
3
4
5
6
7
8
9
10
Input: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 28

Output: False

解题思路：结合BST特点，将BST转化为升序数组，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
private:
    vector<int> res;
public:
    bool findTarget(TreeNode* root, int k) {
        travel(root);
        int i=0;
        int j=res.size()-1;
        while(i<j){
            int sum = res[i]+res[j];
            if(sum > k){
                j--;
            }else if(sum < k){
                i++;
            }else{
                return true;
            }
        }
        return false;
    }
    
    void travel(TreeNode* root){
        if(root == NULL) return;
        travel(root->left);
        res.push_back(root->val);
        travel(root->right);   
    }
};

101. Symmetric Tree

Description:

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

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

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

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

解题思路：代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return root==NULL || isSymmetricHelp(root->left, root->right);
    }
    
    bool isSymmetricHelp(TreeNode* l, TreeNode* r){
        if(l==NULL || r==NULL) return l==r;
        if(l->val != r->val) return false;
        return isSymmetricHelp(l->left, r->right) && isSymmetricHelp(l->right, r->left);
    }
};

563. Binary Tree Tilt

Description:

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:

  1. The sum of node values in any subtree won’t exceed the range of 32-bit integer.
  2. 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
class Solution {
public:
    int result = 0;
    int findTilt(TreeNode* root) {
        postOrder(root);
        return result;
    }
    
    int postOrder(TreeNode* root){
        if(!root) return 0;
        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.

Example 1:
Given tree s:

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

1
2
3
4
  4 
 / \
1   2

true

Example 2:
Given tree s:

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

1
2
3
4
  4
 / \
1   2

false

解题思路：判断高度，判断是否相同，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    vector<TreeNode*> nodes;
    
    bool isSubtree(TreeNode* s, TreeNode* t) {
        
        if(!t && !s){
            return true;
        }
        if(!t || !s){
            return false;
        }
        
        getDepth(s, getDepth(t, -1));
        for(TreeNode* n : nodes){
            if(identical(n, t)){
                return true;
            }
        }
        return false;
    }
    
    int getDepth(TreeNode* r, int d){
        if(!r) return 0;
        int depth = max(getDepth(r->left, d), getDepth(r->right, d)) + 1;
        if(depth == d) nodes.push_back(r);
        return depth;
    }
    
    bool identical(TreeNode* s, TreeNode* t){
        if(!s && !t) return true;
        if(!s || !t || s->val!=t->val) return false;
        return identical(s->left, t->left) && identical(s->right, t->right);
    }
};

671. Second Minimum Node In a Binary Tree

Descripiton:

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.

代码如下：

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
class Solution {
public:
    int findSecondMinimumValue(TreeNode* root) {
        
        if(root->left){
            if(root->left->val < root->right->val){
                int l = findSecondMinimumValue(root->left);
                if(l==-1) return root->right->val;
                return min(l, root->right->val);
            }else if(root->left->val > root->right->val){
                int r = findSecondMinimumValue(root->right);
                if(r==-1) return root->left->val;
                return min(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;
                return min(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.

解题思路：本题需要使用搜索 ，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int longestUnivaluePath(TreeNode* root) {
        int lup = 0;
        if(root) dfs(root, lup);
        return lup;
    }

private:
    int dfs(TreeNode* node, int& lup) {
        int l = node->left ? dfs(node->left, lup) : 0;
        int r = node->right ? dfs(node->right, lup) : 0;
        int resl = node->left && node->left->val == node->val ? l + 1 : 0;
        int resr = node->right && node->right->val == node->val ? r + 1 : 0;
        lup = max(lup, resl + resr);
        return max(resl, resr);
    }
    
};

102. Binary Tree Level Order Traversal

Description:

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],

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

return its level order traversal as:

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

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
/**
 * Definition for a binary tree node.*/
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(root==NULL) return res;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            int n=q.size();
            vector<int> tmp;
            for(int i=0;i<n;i++){
                TreeNode* node=q.front();
                q.pop();
                tmp.push_back(node->val);
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
            res.push_back(tmp);
        }
        return res;
    }
};

103. Binary Tree Zigzag Level Order Traversal

Description:

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],

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

return its zigzag level order traversal as:

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

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <stdio.h>
#include <vector>
#include <stack>
using namespace std;
/**
 * Definition for a binary tree node.*/
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
    vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
        vector<vector<int>> res;
        if(root==NULL) return res;
        stack<TreeNode*> s1;
        stack<TreeNode*> s2;
        int l=1;
        s1.push(root);
        while(!s1.empty()||!s2.empty()){
            vector<int> tmp;
            if(l%2==1){
                while(!s1.empty()){
                    TreeNode* node=s1.top();
                    s1.pop();
                    tmp.push_back(node->val);
                    if(node->left) s2.push(node->left);
                    if(node->right) s2.push(node->right);
                }
            }
            else{
                while(!s2.empty()){
                    TreeNode* node=s2.top();
                    s2.pop();
                    tmp.push_back(node->val);
                    if(node->right) s1.push(node->right);
                    if(node->left) s1.push(node->left);
                }
            }
            l++;
            res.push_back(tmp);
        }
        return res;
    }
};

113. Path Sum II

Description:

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

Note: A leaf is a node with no children.

Example:

Given the below binary tree and sum = 22,

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

Return:

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

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <stdio.h>
#include <vector>
using namespace std;
/**
 * Definition for a binary tree node.*/
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
    
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> res;
        vector<int> tmp;
        getPath(res,tmp,root,sum);
        return res;
    }
    
    void getPath(vector<vector<int>> &res, vector<int> &tmp, TreeNode* root, int remain){
        if(root==NULL){
            return;
        }
        tmp.push_back(root->val);
        if(root->left==NULL && root->right==NULL && root->val==remain) res.push_back(tmp);
        getPath(res,tmp,root->left,remain-root->val);
        getPath(res,tmp,root->right,remain-root->val);
        tmp.pop_back();
        
    }
};

114. Flatten Binary Tree to Linked List

Description:

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

For example, given the following tree:

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

The flattened tree should look like:

1
2
3
4
5
6
7
8
9
10
11
1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
/**
 * Definition for a binary tree node.*/
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
private:
    TreeNode* pre=NULL;
public:
    void flatten(TreeNode* root) {
        if(root==NULL) return;
        flatten(root->right);
        flatten(root->left);
        root->right=pre;
        root->left=NULL;
        pre=root;
    }
};

116. Populating Next Right Pointers in Each Node

Description:

Given a binary tree

1
2
3
4
5
6
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.
  • Recursive approach is fine, implicit stack space does not count as extra space for this problem.
  • You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

Example:

Given the following perfect binary tree,

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

After calling your function, the tree should look like:

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

代码如下：

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
#include <stdio.h>
/**
 * Definition for binary tree with next pointer.*/
struct TreeLinkNode {
   int val;
   TreeLinkNode *left, *right, *next;
   TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
};
class Solution {
public:
    void connect(TreeLinkNode *root) {
        if(root==NULL) return;
        TreeLinkNode* pre=root;
        TreeLinkNode* cur=NULL;
        while(pre->left){
            cur=pre;
            while(cur){
                cur->left->next=cur->right;
                if(cur->next) cur->right->next=cur->next->left;
                cur=cur->next;
            }
            pre=pre->left;
        }
    }
};

117. Populating Next Right Pointers in Each Node II

Description:

Given a binary tree

1
2
3
4
5
6
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.
  • Recursive approach is fine, implicit stack space does not count as extra space for this problem.

Example:

Given the following binary tree,

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

After calling your function, the tree should look like:

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

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <stdio.h>
/**
Definition for binary tree with next pointer.*/
  struct TreeLinkNode {
   int val;
   TreeLinkNode *left, *right, *next;
   TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
};
class Solution {
public:
    void connect(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.

Example 1:

1
2
3
4
5
6
7
8
Input: [1,2,3]

       1
      / \
     2   3

Output: 6

Example 2:

1
2
3
4
5
6
7
8
9
Input: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

Output: 42

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <algorithm>
using namespace std;
/**
 * Definition for a binary tree node.*/
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
private:
    int maxVal;
public:
    int maxPathSum(TreeNode* root) {
        maxVal=INT_MIN;
        maxPathSumDown(root);
        return maxVal;
    }
    
    int maxPathSumDown(TreeNode* node){
        if(node==NULL) return 0;
        int left=max(0,maxPathSumDown(node->left));
        int right=max(0,maxPathSumDown(node->right));
        maxVal=max(maxVal,left+right+node->val);
        return max(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.

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>
/**
 * Definition for a binary tree node.*/
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
private:
    int res=0;
public:
    int sumNumbers(TreeNode* root) {
        return sumNumbersHelp(root,0);
    }
    
    int sumNumbersHelp(TreeNode* node, int n){
        if(!node) return 0;
        if(node->left==NULL && node->right==NULL) return n*10+node->val;
        return sumNumbersHelp(node->left,n*10+node->val)+sumNumbersHelp(node->right,n*10+node->val);
    }
};

144. Binary Tree Preorder Traversal

Description:

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

Example:

1
2
3
4
5
6
7
8
Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,2,3]

代码如下：

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
#include <stdio.h>
#include <vector>
using namespace std;
/**
 * Definition for a binary tree node.*/
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> res;
        preHelp(root,res);
        return res;
    }
    
    void preHelp(TreeNode* root, vector<int> &res){
        if(root==NULL) return;
        res.push_back(root->val);
        preHelp(root->left,res);
        preHelp(root->right,res);
    }
};

145. Binary Tree Postorder Traversal

Description:

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

Example:

1
2
3
4
5
6
7
8
9
Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [3,2,1]

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

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
#include <stdio.h>
#include <vector>
using namespace std;
/**
 * Definition for a binary tree node.*/
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> res;
        postHelp(root,res);
        return res;
    }
    
    void postHelp(TreeNode* root, vector<int> &res){
        if(!root) return;
        postHelp(root->left,res);
        postHelp(root->right,res);
        res.push_back(root->val);
    }
};

173. Binary Search Tree Iterator

Description:

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <stdio.h>
#include <stack>
using namespace std;
/**
 * Definition for binary tree*/
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class BSTIterator {
private:
    stack<TreeNode*> st;
public:
    BSTIterator(TreeNode *root) {
        pushAll(root);
    }
    
    void pushAll(TreeNode* node){
        for(;node!=NULL;st.push(node),node=node->left);
    }
    /** @return whether we have a next smallest number */
    bool hasNext() {
        return !st.empty();
    }
    
    /** @return the next smallest number */
    int next() {
        TreeNode* tmp=st.top();
        st.pop();
        pushAll(tmp->right);
        return tmp->val;
    }
};

199. Binary Tree Right Side View

Description:

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.

Example:

1
2
3
4
5
6
7
8
9
Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:

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

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <stdio.h>
#include <queue>
#include <vector>
using namespace std;
/**
 * Definition for a binary tree node.*/
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> res;
        if(root==NULL) return res;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            int n=q.size();
            for(int i=0;i<n;i++){
                TreeNode* tmp=q.front();
                if(i==n-1) res.push_back(tmp->val);
                q.pop();
                if(tmp->left) q.push(tmp->left);
                if(tmp->right) q.push(tmp->right);
            }
        }
        return res;
    }
};

236. Lowest Common Ancestor of a Binary Tree

Description:

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]

1
2
3
4
5
6
7
8
     _______3______
    /              \
 ___5__          ___1__
/      \        /      \
6      _2       0       8
      /  \
      7   4

Example 1:

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

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <stdio.h>

/**
 * Definition for a binary tree node.*/
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==NULL || root==p || root==q) return root;
        TreeNode* left=lowestCommonAncestor(root->left,p,q);
        TreeNode* right=lowestCommonAncestor(root->right,p,q);
        return !left?right:!right?left:root;
    }
};

94. Binary Tree Inorder Traversal

Description:

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

Example:

1
2
3
4
5
6
7
8
Input: [1,null,2,3]
   1
    \
     2
    /
   3

Output: [1,3,2]

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

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <stdio.h>
#include <vector>
#include <stack>
using namespace std;
/**
 * Definition for a binary tree node.*/
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> sta;
        if(root==NULL) return res;
        TreeNode* curr=root;
        while(!sta.empty()||curr){
            if(curr){
                sta.push(curr);
                curr=curr->left;
            }else{
                TreeNode* node=sta.top();
                sta.pop();
                res.push_back(node->val);
                curr=node->right;
            }
        }
        return res;
    }
};

98. Validate Binary Search Tree

Description:

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:

1
2
3
4
5
6
Input:
    2
   / \
  1   3
Output: true

Example 2:

1
2
3
4
5
6
7
8
    5
   / \
  1   4
     / \
    3   6
Output: false
Explanation: The input is: [5,1,4,null,null,3,6]. The root node's value
             is 5 but its right child's value is 4.

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>
/**
 * Definition for a binary tree node.*/
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        TreeNode* pre=NULL;
        return validate(root, pre);
    }
    
    bool validate(TreeNode* root, TreeNode* &pre){
        if(root==NULL) return true;
        if(!validate(root->left, pre)) return false;
        if(pre!=NULL && pre->val>=root->val) return false;
        pre=root;
        return validate(root->right,pre);
    }
};

99. Recover Binary Search Tree

Description:

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

Recover the tree without changing its structure.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Input: [1,3,null,null,2]

   1
  /
 3
  \
   2

Output: [3,1,null,null,2]

   3
  /
 1
  \
   2

Example 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Input: [3,1,4,null,null,2]

  3
 / \
1   4
   /
  2

Output: [2,1,4,null,null,3]

  2
 / \
1   4
   /
  3

Follow up:

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

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>
#include <algorithm>
#include <limits.h>
using namespace std;
/**
 * Definition for a binary tree node.*/
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
    TreeNode* first=NULL;
    TreeNode* second=NULL;
    TreeNode* prev = new TreeNode(INT_MIN);
public:
    void recoverTree(TreeNode* root) {
        help(root);
        swap(first->val, second->val);
    }
    
    void help(TreeNode* root){
        if(root==NULL)  return;
        help(root->left);
        if(first==NULL && prev->val >= root->val)   first=prev;
        if(first!=NULL && prev->val >= root->val)   second=root;
        prev=root;
        help(root->right);
    }
};

ciicA BOCer

个人简介