字数统计: 2.5k字   |   阅读时长: 12分

二叉树(3)

递归三步曲：

  1. 确定递归函数的参数和返回类型
  2. 确定终止条件
  3. 确定单层递归的逻辑

404. 左叶子之和 - 力扣（LeetCode） (leetcode-cn.com)

给定二叉树的根节点 root ，返回所有左叶子之和。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//递归法
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
        if(root == NULL)    return 0;
        int leftVal = sumOfLeftLeaves(root->left);
        int rightVal = sumOfLeftLeaves(root->right);
        int midVal = 0;
        if(root->left != NULL && root->left->left == NULL && root->left->right == NULL)
        midVal = root->left->val;
        return midVal + leftVal + rightVal;
    }
};
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
//迭代法, 先序遍历，(不是必须先序遍历，中左右和中右左均可)
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumOfLeftLeaves(TreeNode* root) {
       stack <TreeNode*> st;
       int result = 0;
       if(root == NULL) return 0;
       st.push(root);
       while(!st.empty())
       {
           TreeNode *node = st.top();
           st.pop();
           if(node->left != NULL && node->left->left == NULL && node->left->right == NULL)
           result = result + node->left->val;
           if(node->right != NULL)  st.push(node->right); 
           if(node->left != NULL)   st.push(node->left);      
       }
       return result; 
    }
};

112. 路径总和 - 力扣（LeetCode） (leetcode-cn.com)

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 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
//递归法
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    bool traversal(TreeNode *cur, int count) //count记录目标值减掉cur节点前的所有值得到的值
    {
        if(!cur->left && !cur->right && count == 0) return true;
        if(!cur->left && !cur->right)   return false;
        if(cur->left != NULL)
        {
            if(traversal(cur->left, count - cur->left->val) == true)   return true;//注意这里隐藏了回溯，递归中第二个变量改变，但是count的值没有变
        }
        if(cur->right != NULL)
        {
            if(traversal(cur->right, count - cur->right->val) == true)  return true;
        }
        return false;
    }
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(root == NULL)    return false;
        return traversal(root, targetSum - root->val);//注意要减掉根节点
    }
};
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
//迭代法，注意为了同时保存树的节点和其值使用了pair，计算每条路径的值求和如果等于target就返回true，否则返回false。
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int targetSum) {
        if(root == NULL)    return false;
        stack <pair<TreeNode*, int>> st;
        st.push(pair<TreeNode*, int>(root, root->val));
        while(!st.empty())
        {
            pair<TreeNode*, int> node = st.top();
            st.pop();
            if(!node.first->left && !node.first->right && node.second == targetSum)
            return true;
            if(node.first->right != NULL)
            st.push(pair<TreeNode*, int>(node.first->right, node.second + node.first->right->val));
            if(node.first->left != NULL)
            st.push(pair<TreeNode*, int>(node.first->left, node.second + node.first->left->val));
        }
        return false;
    }
};

513. 找树左下角的值 - 力扣（LeetCode） (leetcode-cn.com)

给定一个二叉树的 根节点 root，请找出该二叉树的 最底层 最左边 节点的值。

假设二叉树中至少有一个节点。

层序遍历，只需要在循环时每次都记录第一个元素的值，最后result就会被最后一行的第一个元素值覆盖。

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
//迭代法
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        if(root == NULL)    return true;
        queue <TreeNode*> que;
        que.push(root);
        int result = 0;
        while(!que.empty())
        {
            int size = que.size();
            for(int i = 0; i < size; i++)
            {
            TreeNode* node = que.front();
            que.pop();
            if(i == 0) result = node->val;
            if(node->left != NULL) que.push(node->left);
            if(node->right != NULL) que.push(node->right); 
            }
        }
        return result;
    }
};

如果使用递归法，如何判断是最后一行呢，其实就是深度最大的叶子节点一定是最后一行。那么如果找最左边的呢？可以使用前序遍历，这样才先优先左边搜索，然后记录深度最大的叶子节点，此时就是树的最后一行最左边的值。

递归函数的返回值问题：如果需要遍历整棵树，递归函数就不能有返回值。如果需要遍历某一条固定路线，递归函数就一定要有返回值！

此题要找最深的叶子节点，需要遍历整棵树，因此递归函数不能有返回值。

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxLen = INT_MIN;
    int maxleftValue;
    void traversal(TreeNode* root, int leftLen)
    {
        if(root->left == NULL && root->right == NULL)
        {
            if(leftLen > maxLen)
            {
                maxLen = leftLen;
                maxleftValue = root->val;
            }
            return;
        }
        if(root->left != NULL)
        traversal(root->left, leftLen + 1);
        if(root->right != NULL)
        traversal(root->right, leftLen + 1);
        return;
    }
    int findBottomLeftValue(TreeNode* root) {
        traversal(root, 0);
        return maxleftValue;
    }
};

113. 路径总和 II - 力扣（LeetCode） (leetcode-cn.com)

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void traversal(TreeNode* node, int count)
    {
        if(node->left == NULL && node->right == NULL && count == 0)
        {
        result.push_back(path);
        return;
        }
        if(node->left == NULL && node->right == NULL)
        return;
        if(node->left != NULL)
        {
            path.push_back(node->left->val);
            traversal(node->left, count - node->left->val);//隐藏着回溯
            path.pop_back();
        }
        if(node->right != NULL)
        {
            path.push_back(node->right->val);
            traversal(node->right, count - node->right->val);
            path.pop_back();
        }
        return;
    }
public:
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        if(root == NULL)    return result;
        path.push_back(root->val);
        traversal(root, targetSum - root->val);
        return result;
    }
};

106. 从中序与后序遍历序列构造二叉树 - 力扣（LeetCode） (leetcode-cn.com)

给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。

  • 第一步：如果数组大小为零的话，说明是空节点了。
  • 第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
  • 第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
  • 第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
  • 第五步：切割后序数组，切成后序左数组和后序右数组
  • 第六步：递归处理左区间和右区间
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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    TreeNode* traversal(vector <int> &inorder, vector <int> &postorder)
    {
        if(postorder.size() == 0)   return NULL;
        //后序遍历的最后一个节点，对应二叉树的根节点
        int rootVal = postorder[postorder.size() - 1];
        TreeNode* root = new TreeNode(rootVal);
        //如果就1个节点，结束循环
        if(postorder.size() == 1)
        return root;
        int delimitIndex;
        //找到根节点在中序遍历中的位置
        for(delimitIndex = 0; delimitIndex < inorder.size(); delimitIndex++)
        if(inorder[delimitIndex] == rootVal) break;
        //切割中序数组
        vector <int> leftInorder(inorder.begin(), inorder.begin() + delimitIndex);
        vector <int> rightInorder(inorder.begin() + delimitIndex + 1, inorder.end());
        //切割后序数组,后序数组的左边和中序数组的左边元素个数相同
        postorder.resize(postorder.size() - 1);
        vector <int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
        vector <int> rightPostorder(postorder.begin() + leftInorder.size(), postorder.end());
        root->left = traversal(leftInorder, leftPostorder);
        root->right = traversal(rightInorder, rightPostorder);
        return root;
    }
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) 
    {
        if(inorder.size() == 0 || postorder.size() == 0)    return NULL;
        return traversal(inorder, postorder);
    }
};

654. 最大二叉树 - 力扣（LeetCode） (leetcode-cn.com)

给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从nums 递归地构建:

创建一个根节点，其值为 nums 中的最大值。
递归地在最大值 左边 的 子数组前缀上 构建左子树。
递归地在最大值 右边 的 子数组后缀上 构建右子树。
返回 nums构建的 最大二叉树 。

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
        TreeNode* node = new TreeNode(0);
        if(nums.size() == 1)
        {
        node->val = nums[0];
        return node;
        }
        int maxVal = INT_MIN;
        int maxvalIndex = 0;
        for(int i = 0; i < nums.size(); i++)
        {
            if(nums[i] > maxVal)    //找到最大值记录其值和下标
            {
                maxVal = nums[i];
                maxvalIndex = i;
            }
        }
        node->val = maxVal; //将最大值赋给根节点
        if(maxvalIndex > 0)
        {
            vector <int> newVec(nums.begin(), nums.begin() + maxvalIndex);
            node->left = constructMaximumBinaryTree(newVec);    //递归，在最大值左边的子数组前缀上构建左子树
        }
        if(maxvalIndex < (nums.size() - 1))
        {
            vector <int> newVec(nums.begin() + maxvalIndex + 1, nums.end());
            node->right = constructMaximumBinaryTree(newVec);   ////递归，在最大值右边的子数组前缀上构建右子树
        }
        return node; 
    }
};

扫一扫，分享到微信

微信分享二维码
本站总访问量次 |

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

这一定是一个<br><br>很长很长的一生啊