Binary Tree & Recursion

发表于 | 更新于: | 分类于 | | 阅读次数:
字数统计: 1,213 | 阅读时长 ≈ 7

二叉树天然有着递归的结构，二叉树的定义即使用了递归

1
2
3
4
5
6
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) val(x), left(NULL), right(NULL) {}
};

例题：二叉树的最大深度

1
2
3
4
int maxDepth(TreeNode* root) {
    if (root == NULL) return 0;
    return max(maxDepth(root -> left), maxDepth(root -> right)) + 1;
}

LeetCode练习题
No.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
8
9
10
class Solution {
public:
    int minDepth(TreeNode* root) {
        if (root == NULL) return 0;
        if (root -> left == NULL && root -> right == NULL) return 1;
        else if (root -> left && root -> right == NULL) return minDepth(root -> left) + 1;
        else if (root -> left == NULL && root -> right) return minDepth(root -> right) + 1;
        else return min(minDepth(root -> left), minDepth(root -> right)) + 1;
    }
};

例题： 翻转二叉树

1
2
3
4
5
6
7
8
TreeNode* invertTree(TreeNode* root) {
    if (root) {
        TreeNode *left = invertTree(root -> left);
        root -> left = invertTree(root -> right);
        root -> right = left;            
    }
    return root;
}

LeetCode练习题：

  • No.100 SameTree
  • No.101 Symmetric Tree
  • No.222 Count Complete Tree Nodes
  • No.110 Balanced Binary Tree

递归的终止条件
例题: Path Sum

坑：还在叶子节点

1
2
3
4
5
6
7
8
bool hasPathSum(TreeNode* root, int sum) {
    //if (root == NULL) return (sum == 0);
    if (root == NULL) return false;
    if (root -> left == NULL && root -> right == NULL) return (sum == root -> val);
    
    return hasPathSum(root -> left, sum - root -> val) || hasPathSum(root -> right, sum - root -> val);
}

LeetCode练习题：

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

递归的返回值
例题：257. Binary Tree Paths

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<string> binaryTreePaths(TreeNode* root) {        
    if (root == NULL) return {};   
    vector<string> res;
    string tmp = to_string(root -> val);
    if (root -> left == NULL && root -> right == NULL) res.push_back(tmp);        
    vector<string> left = binaryTreePaths(root -> left);
    for (auto iter = left.begin(); iter != left.end(); iter ++) res.push_back(tmp + "->" + *(iter));
    vector<string> right = binaryTreePaths(root -> right);
    for (auto iter = right.begin(); iter != right.end(); iter ++) res.push_back(tmp + "->" + *(iter));
        
    return res;
}

LeetCode练习题：

  • No.113 Path Sum II

    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
    class Solution {
    public:
        vector<vector<int>> pathSumHelper(TreeNode* root, int sum) {
            if (root == NULL) return {};
            vector<vector<int>> res;
            if (root -> left == NULL && root -> right == NULL) {
                if (sum == root -> val) res.push_back({sum});
                return res;
            }
            int newSum = sum - root -> val;
            vector<vector<int>> left = pathSumHelper(root -> left, newSum);
            for (auto &v: left) {
                if (!v.empty()) {
                    v.push_back(root -> val);
                    res.push_back(v);
                }
            }            
            
            vector<vector<int>> right = pathSumHelper(root -> right, newSum);
            for (auto &v: right) {
                if (!v.empty()) {
                    v.push_back(root -> val);
                    res.push_back(v);                
                }
            }            
            
            return res;   
        }
        vector<vector<int>> pathSum(TreeNode* root, int sum) {
            vector<vector<int>> res = pathSumHelper(root, sum);
            for (auto &v: res) {
                reverse(v.begin(), v.end());
            }
            return res;
        }
    };

  • No.129 Sum Root to Leaf Numbers

    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
    48
    49
    50
    51
    class Solution {
    public:
        int str2num(string s) {
            int res = 0;
            for(int i = 0; i < s.size(); i++) {
                res = res * 10 + s[i] - '0';
            }
            return res;
        }
        vector<string> sumNumbersHelper(TreeNode* root) {
            if (root == NULL) return {};
            vector<string> res;
            string s_val = to_string(root -> val);
            if (root -> left == NULL && root -> right == NULL){
                res.push_back(s_val);
            } 
            vector<string> left = sumNumbersHelper(root -> left);
            for (auto &s: left) {
                res.push_back(s_val + s);
            }
            vector<string> right = sumNumbersHelper(root -> right);
            for (auto &s: right) {
                res.push_back(s_val + s);
            }
            return res;
        }
        int sumNumbers(TreeNode* root) {
            vector<string> str_num = sumNumbersHelper(root);
            int res = 0;
            for (auto s : str_num) {
                int tmp = str2num(s);
                res += tmp;
            }
            return res;
        }
    };
    //下面这个更值得学习
    class Solution {
    public:
        
        int helper(TreeNode* root, int val) {
            if (!root) return 0;
            auto v = val*10 + root->val;
            if (!root->left && !root->right) return v;
            return helper(root->left, v) + helper(root->right, v);
            
        }
        int sumNumbers(TreeNode* root) {
            return helper(root, 0);
        }
    };

复杂递归问题

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
//一种错误的做法
int pathSumIII(TreeNode* root, int sum) {
   return func(root, sum);
}
    int func(TreeNode* root,  int sum) {
        int count = 0;
        if (root == NULL) {
            return (sum == 0) ? 1 : 0;
        }
        if (sum == root -> val) {
            count += 1;
        }
        
        count += func(root -> left, sum - root -> val) + func(root -> right, sum - root -> val);
        count += func(root -> left, sum) + func(root -> right, sum);   	//在递归中会重复计算这一个过程
        return count;
    }
    
//正确的做法
class Solution {
public:
    int pathSum(TreeNode* root, int sum) {       
        if (root == NULL) return 0;
            
        int count = 0;
        count += func(root, sum);
        count += pathSum(root -> left, sum) + pathSum(root -> right, sum);   	
        return count;
    }
    int func(TreeNode* root,  int sum) {
        int count = 0;
        if (root == NULL) return 0;
        if (sum == root -> val) count += 1;
        
        count += func(root -> left, sum - root -> val) + func(root -> right, sum - root -> val);
        return count;
    }    
};

二分搜索树(Binary Search Tree)

  • 基本操作：

    插入(insert)
    查找(find)
    删除(delete)

  • 实现的功能：

    最大、最小
    前驱、后继
    上界、下界
    某个元素的排序
    寻找第K大(小)元素

用途：map，set
数据库底层实现：平衡二分搜索树

例题： No.235 Lowest Common Ancestor of a Binary Search Tree

1
2
3
4
5
6
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == NULL) return NULL;
    if (p -> val < root -> val && q -> val < root -> val) return lowestCommonAncestor(root -> left, p, q);
    if (p -> val > root -> val && q -> val > root -> val) return lowestCommonAncestor(root -> right, p, q);
    return root;
}

此题引申到普通二叉树，以下代码在LeetCode上通过(速度感人)

1
2
3
4
5
6
7
8
9
10
11
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
    if (root == NULL) return NULL;
    if (findTreeNode(root -> left, p) && findTreeNode(root -> left, q)) return lowestCommonAncestor(root -> left, p, q);
    if (findTreeNode(root -> right, p) && findTreeNode(root -> right, q)) return lowestCommonAncestor(root -> right, p, q);
    return root;
}
bool findTreeNode(TreeNode* root, TreeNode* node) {
    if (root == NULL) return false;
    if (root == node) return true;
    return findTreeNode(root -> left, node) || findTreeNode(root -> right, node);
}

LeetCode练习题：

  • No.98 Validate Binary Search Tree
  • No.450 Delete Node in a BST
  • No.108 Convert Sorted Array to Binary Search Tree
  • No.230 Kth Smallest Elemment in a BST
  • No.236 Lowest Common Ancestor of a Binary Tree
    1
    2
    3
    4
    5
    6
    7
    8
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == NULL) return NULL;
        if (root == p || root == q) return root;
        TreeNode* left = lowestCommonAncestor(root -> left, p, q);
        TreeNode* right = lowestCommonAncestor(root -> right, p, q);
        if (left && right) return root;
        return left? left : right;
    }

总结：跟叶子节点相关的问题，需要判断其左右子节点