Solve binary tree (6)

404. Sum of left leaves

summary ：

It's possible that both left and right children have left leaves .

class Solution {
    
public:
    int sumOfLeftLeaves(TreeNode* root) {
    
        if (root == NULL) return 0;
        int midValue = 0;
        if (root->left != NULL && root->left->left == NULL && root->left->right == NULL) {
    
            midValue = root->left->val;
        }
        return midValue + sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);
    }
};

513. Find the value in the lower left corner of the tree

If you need to traverse the whole tree , A recursive function cannot have a return value . If you need to traverse a fixed route , A recursive function must have a return value ！

summary ：

if Left and right children are empty , Add return .

   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; // Forget to write .
            }
            if (root->left) {
    
                leftLen++;
                traversal(root->left, leftLen);
                leftLen--; //  to flash back 
            }
            if (root->right) {
    
                leftLen++;
                traversal(root->right, leftLen);
                leftLen--; //  to flash back 
            }
            return;
        }
        int findBottomLeftValue(TreeNode* root) {
    
            traversal(root, 0);
            return maxleftValue;
        }
    };

Iterative method

Sequence traversal is most appropriate for this problem , Better understood than recursion ！

Just record the value of the first node in the last line .

If you don't know about sequence traversal , Look at this , The template of sequence traversal is also given in this article , With a little modification, I'll brush this question .

The code is as follows ：

 class Solution {
    
    public:
        int findBottomLeftValue(TreeNode* root) {
    
            queue<TreeNode*> que;
            if (root != NULL) 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; //  Record the first element in the last line 
                    if (node->left) que.push(node->left);
                    if (node->right) que.push(node->right);
                }
            }
            return result;
        }
    };

112. The sum of the paths

summary ：

too strong .

  class solution {
    
    private:
        bool traversal(treenode* cur, int count) {
    
            if (!cur->left && !cur->right && count == 0) return true; //  Leaf node encountered , And the count is 0
            if (!cur->left && !cur->right) return false; //  When a leaf node is encountered, it returns directly 
    
            if (cur->left) {
     //  Left 
                count -= cur->left->val; //  recursive , Processing nodes ;
                if (traversal(cur->left, count)) return true;
                count += cur->left->val; //  to flash back , Cancel processing result 
            }
            if (cur->right) {
     //  Right 
                count -= cur->right->val; //  recursive , Processing nodes ;
                if (traversal(cur->right, count)) return true;
                count += cur->right->val; //  to flash back , Cancel processing result 
            }
            return false;
        }
    
    public:
        bool haspathsum(treenode* root, int sum) {
    
            if (root == null) return false;
            return traversal(root, sum - root->val);
        }
    };



 Reduced Edition ：

    class solution {
    
    public:
        bool haspathsum(treenode* root, int sum) {
    
            if (root == null) return false;
            if (!root->left && !root->right && sum == root->val) {
    
                return true;
            }
            return haspathsum(root->left, sum - root->val) || haspathsum(root->right, sum - root->val);
        }
    };

iteration ：

Just for us pair Structure to store the elements in this stack .

Defined as ：pair<treenode*, int> pair< Node pointer , Path value >

   lass solution {
    
    
    public:
        bool haspathsum(treenode* root, int sum) {
    
            if (root == null) return false;
            //  At this time, what should be put in the stack is pair< Node pointer , Path value >
            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 the node is a leaf node , At the same time, the path value of this node is equal to sum, So return true
                if (!node.first->left && !node.first->right && sum == node.second) return true;
    
                //  Right node , When pressing in a node , Record the path value of the node 
                if (node.first->right) {
    
                    st.push(pair<treenode*, int>(node.first->right, node.second + node.first->right->val));
                }
    
                //  The left node , When pressing in a node , Record the path value of the node 
                if (node.first->left) {
    
                    st.push(pair<treenode*, int>(node.first->left, node.second + node.first->left->val));
                }
            }
            return false;
        }
    };

113. The sum of the paths 2

summary ： Determine whether there is a path , This is to record the route . I'm a little strange. Won't it coincide ？

class solution {
    
private:
    vector<vector<int>> result;
    vector<int> path;
    //  Recursive functions do not need to return values , Because we have to traverse the whole tree 
    void traversal(treenode* cur, int count) {
    
        if (!cur->left && !cur->right && count == 0) {
     //  A leaf node is encountered and the sum is found sum The path of 
            result.push_back(path);
            return;
        }

        if (!cur->left && !cur->right) return ; //  Encountered a leaf node and didn't find a suitable edge , Go straight back to 

        if (cur->left) {
     //  Left  （ Empty nodes are not traversed ）
            path.push_back(cur->left->val);
            count -= cur->left->val;
            traversal(cur->left, count);    //  recursive 
            count += cur->left->val;        //  to flash back 
            path.pop_back();                //  to flash back 
        }
        if (cur->right) {
     //  Right  （ Empty nodes are not traversed ）
            path.push_back(cur->right->val);
            count -= cur->right->val;
            traversal(cur->right, count);   //  recursive 
            count += cur->right->val;       //  to flash back 
            path.pop_back();                //  to flash back 
        }
        return ;
    }

public:
    vector<vector<int>> pathsum(treenode* root, int sum) {
    
        result.clear();
        path.clear();
        if (root == null) return result;
        path.push_back(root->val); //  Put the root node into the path 
        traversal(root, sum - root->val);
        return result;
    }
};

106. Construct binary tree from middle order and post order traversal sequence

summary ：B The video explanation on the station is very easy to segment Array .

The last node of the subsequent sequence is the root node , According to this, the two sequences can be divided , Get the post order sequence and middle order sequence of the left and right subtrees , Then recursively construct left and right subtrees .

Code

    /** * 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 {
    
        unordered_map<int, int> pos;
    public:
        TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
    
            int n = inorder.size();
            for (int i = 0; i < n; i++) pos[inorder[i]] = i;
            return build(inorder, postorder, 0, n - 1, 0, n - 1);
        }
    
        TreeNode* build(vector<int>& inorder, vector<int>& postorder, int il, int ir, int pl, int pr) {
    
            if (il > ir || pl > pr) return nullptr;
    
            int k = pos[postorder[pr]] - il; // From the last position in the sequence , Find the position of the middle order , Subtracting the starting position is the number ,
    
            TreeNode* root = new TreeNode(postorder[pr]);
            root->left = build(inorder, postorder, il, il + k - 1, pl, pl + k - 1);
            root->right = build(inorder, postorder, il + k + 1, ir, pl + k, pr - 1);
    
            return root;
        }
    };

 Random code recording ;

    class Solution {
    
    private:
        TreeNode* traversal (vector<int>& inorder, vector<int>& postorder) {
    
            if (postorder.size() == 0) return NULL;
    
            //  After traversing the last element of the array , Is the current intermediate node 
            int rootValue = postorder[postorder.size() - 1];
            TreeNode* root = new TreeNode(rootValue);
    
            //  Leaf node 
            if (postorder.size() == 1) return root;
    
            //  Find the cutting point of the middle order traversal 
            int delimiterIndex;
            for (delimiterIndex = 0; delimiterIndex < inorder.size(); delimiterIndex++) {
    
                if (inorder[delimiterIndex] == rootValue) break;
            }
    
            //  Cut the ordered array 
            //  Left closed right open interval ：[0, delimiterIndex)
            vector<int> leftInorder(inorder.begin(), inorder.begin() + delimiterIndex);
            // [delimiterIndex + 1, end)
            vector<int> rightInorder(inorder.begin() + delimiterIndex + 1, inorder.end() );
    
            // postorder  Discard end element 
            postorder.resize(postorder.size() - 1);
    
            //  Cut sequential array 
            //  Still left closed and right open , Note that the size of the left middle order array is used as the cutting point 
            // [0, leftInorder.size)
            vector<int> leftPostorder(postorder.begin(), postorder.begin() + leftInorder.size());
            // [leftInorder.size(), end)
            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);
        }
    };