当前位置：网站首页>Summary of binary tree exercises

According to the result of middle order traversal [2,1,4,3,5] And the result of postorder traversal [2,4,5,3,1] Construct a binary tree {1,2,3,#,#,4,5}

2. The idea diagram

Because the last element of the postorder traversal is the root node , So we can determine the root node according to the post order sequence , Then find the root node from the middle order traversal , Then divide the interval , Finally, the left and right subtrees of the current root node can be constructed recursively according to the interval .

3. Code

    public TreeNode buildTree (int[] inorder, int[] postorder) {
        // write code here
        return build(inorder, 0, inorder.length, postorder, 0, postorder.length);
    }
    public TreeNode build(int[] inorder, int inLeft, int inRight, int[] postorder, int postLeft, int postRight) {
        // It indicates that the left and right subtrees of the current interval have been constructed 
        if(inRight-inLeft<1) {
            return null;
        }
        // This indicates that there is only one node left of the current subtree , Construct directly as the root node 
        if(inRight-inLeft==1) {
            return new TreeNode(inorder[inLeft]);
        }
        // Find the location of the root node in the ordered array 
        int pos = 0;
        for(int i=inLeft; i<inRight; i++) {
            if(inorder[i] == postorder[postRight-1]) {
                pos = i;
                break;
            }
        }
        TreeNode root = new TreeNode(inorder[pos]);
        // Find the location of the root node , Start to divide the interval between the mid order array and the post order array 
        root.left = build(inorder, inLeft, pos, postorder, postLeft, postLeft+(pos-inLeft));
        root.right = build(inorder, pos+1, inRight, postorder, postLeft+(pos-inLeft), postRight-1);
        return root;
    }

Two . Traversing from front order and middle order to construct binary tree

1. subject

Given two arrays of integers preorder and inorder , among preorder Is the prior traversal of a binary tree , inorder Is the middle order traversal of the same tree , Please construct a binary tree and return its root node .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Example ：

Input : preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output : [3,9,20,null,null,15,7]

2. The idea diagram

The idea of dividing intervals ： The first thing to use here is map To save the values and subscripts of the middle order array , It is convenient to find the middle order position to divide the interval ; Then recursively construct a binary tree , The left boundary of the current order = Right border , This indicates that the current interval has been constructed , Go straight back to , Otherwise, according to the previous order （ The first node of the subinterval of the preorder is the root node ） Construct the root node , Then recursively construct the left and right subtrees of the root node , Finally, return to the root node .

3. Code

     Map<Integer, Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for(int i=0; i<inorder.length; i++) {
            map.put(inorder[i], i);
        }
       return dfs(preorder, 0,preorder.length, inorder, 0, inorder.length);
        
    }
    public TreeNode dfs(int[] preorder, int preLeft, int preRight, int[] inorder, int inLeft, int inRight){
        if(inRight-inLeft==0) {
            return null;
        }
        
        // Get the position of the middle order traversal 
        int pos = map.get(preorder[preLeft]);
        // Divide the interval and construct the root node 
        TreeNode root = new TreeNode(inorder[pos]);
        root.left = dfs(preorder, preLeft+1, preLeft+(pos-inLeft)+1, inorder, inLeft, pos);
        root.right = dfs(preorder, preLeft+(pos-inLeft)+1, preRight, inorder, pos+1, inRight);
        return root;
    }

3、 ... and . The maximum path sum of a binary tree

1. subject

route It is defined as a path starting from any node in the tree , Along the parent node - Child node connection , A sequence that reaches any node . The same node in a path sequence At most once . This path At least one node , And it doesn't have to go through the root node .

Path and Is the sum of the values of the nodes in the path .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/binary-tree-maximum-path-sum
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Example ：

2. The idea diagram

3. Code

 int maxRes = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        dfs(root);
        return maxRes;
    }
    public int dfs(TreeNode root) {
        // Empty nodes do not contribute 
        if(root == null) {
            return 0;
        }
        // Count the contribution of left and right subtrees , If it is less than 0 No statistics 
        int left = Math.max(dfs(root.left),0);
        int right = Math.max(dfs(root.right),0);
        // Determine whether the value of the current path is greater than the saved result value 
        maxRes = Math.max(maxRes, root.val+left+right);
        
        // Returns the maximum path and in the current subtree 
        return root.val+Math.max(left, right);
        
    }

Four . Bracket generation

1. subject

Numbers n Represents the logarithm of the generated bracket , Please design a function , Used to be able to generate all possible and Effective Bracket combination .

Example ：

 Input ：n = 3
 Output ：["((()))","(()())","(())()","()(())","()()()"]

2. The idea diagram

First, recursively handle the left parenthesis , After processing the left parenthesis , The right bracket should be handled according to the left bracket , When the number of left parentheses is more than that of right parentheses , Then deal with the closing parenthesis , It is equivalent to that the left bracket matches first , Because you have to have the left parenthesis first , Then the right parenthesis can match , The processing diagram is as follows ：

3. Code

  public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        dfs(n, n, new StringBuilder(), res);
        return res;
    }
    public void dfs(int left, int right, StringBuilder sb, List<String> res) {
        if(left==0 && right==0) {
            res.add(new String(sb));
            return;
        }
        if(left>0) {
            sb.append('(');
            dfs(left-1, right, sb, res);
            sb.deleteCharAt(sb.length()-1);
        }
        if(right>left) {
            sb.append(')');
            dfs(left, right-1, sb, res);
            sb.deleteCharAt(sb.length()-1);
        }
    }

5、 ... and . Different binary search trees

1. subject

Give you an integer n , Seek just by n Composed of nodes with node values from 1 To n Different from each other Binary search tree How many kinds? ？ Returns the number of binary search trees satisfying the meaning of the question .

Example ：

2. The idea diagram

The binary search tree is the node of the left subtree < Current root node < Node of right subtree ; Because each can be the root node , Therefore, the number of all binary search trees that can be formed with the current node as the root node is calculated each time , Then sum all the results ; The way to find the number of binary search trees for the current node is ： First find the number of binary search trees composed of the left nodes of the current node , Then find the number of binary search trees composed of the nodes on the right of the current node , Last left * The number on the right is the number of binary search trees of the current node .

Optimize ： Because each element will be the root node , So the binary search tree in some subtrees is solved repeatedly , With the help of map Set to save the binary search tree , If the binary search tree of the current node has been solved , It's right there map Take it out , Otherwise, add it to map in .

3. Code

（1） Before optimization

public int numTrees(int n) {
        // The root node is only 1 Or 0 individual 
        if(n==0 || n==1) {
            return 1;
        }
        int count = 0;
        for(int i=1; i<=n ;i++) {
            // Calculate the number of left and right subtrees with the current node as the root node 
            int leftCount = numTrees(i-1);
            int rightCount = numTrees(n-i);
            count += leftCount*rightCount;
        }
        return count;
    }

（2） After optimization

// Set to global variable , Keep records  
HashMap<Integer,Integer> map = new HashMap<>();
    public int numTrees(int n) {
        // The root node is only 1 Or 0 individual 
        if(n==0 || n==1) {
            return 1;
        }
        // It indicates that the number of binary search trees with the current root has been searched 
        if(map.containsKey(n)) {
            return map.get(n);
        }
        int count = 0;
        for(int i=1; i<=n ;i++) {
            // Calculate the number of left and right subtrees with the current node as the root node 
            int leftCount = numTrees(i-1);
            int rightCount = numTrees(n-i);
            count += leftCount*rightCount;
        }
        map.put(n, count);
        return count;
    }

6、 ... and . Verify binary search tree

1. subject

Give you the root node of a binary tree root , Determine whether it is an effective binary search tree .

It works The binary search tree is defined as follows ：

The left subtree of the node contains only Less than Number of current nodes .
The right subtree of the node contains only Greater than Number of current nodes .
All left and right subtrees themselves must also be binary search trees .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/validate-binary-search-tree
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

2. The idea diagram

According to the properties of binary search tree ： Left < At present < Right , The result of middle order is ordered , So keep the previous node when searching , Then the value of the current node is compared with the value of the previous node , If the value of the previous node >= The value of the current node , Explain the non-conforming results , return false; The final processing method is to process the left subtree first , If the left subtree does not satisfy the condition , Go straight back to false; If the left subtree is ordered , Then the current node will be processed , Then we can deal with the right subtree .

3. Code

 TreeNode pre = null;
    public boolean isValidBST(TreeNode root) {
        if(root == null) {
            return true;
        }
        // It shows that the left subtree does not satisfy the property of binary tree , Go straight back to 
        if(!isValidBST(root.left)) {
            return false;
        }
        // Judge the size of the current node and the previous node 
        if(pre!=null && pre.val>= root.val) {
            return false;
        }
        pre = root;
        // Regardless of the right subtree , Go straight back to 
        return isValidBST(root.right);
    }

7、 ... and . The binary tree is expanded into a list

1. subject

Give you the root node of the binary tree root , Please expand it into a single linked list ：

The expanded single linked list should also be used TreeNode , among right The child pointer points to the next node in the list , The left sub pointer is always null .
The expanded single linked list should be the same as the binary tree The first sequence traversal Same order .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/flatten-binary-tree-to-linked-list
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Example ：

2. The idea diagram

Preorder traversal saves all nodes , Then the previous node is the precursor (pre), Modified first pre.left It's empty , And then let pre.right Point to the current node （cur）, The final result is a single linked list .

3. Code

public void flatten(TreeNode root) {
        List<TreeNode> list = new ArrayList<>();
        preorder(root, list);
        // The first node is the precursor node , Modify the... Of the previous node left by null, right Point to the current node 
        for(int i=1; i<list.size(); i++) {
            TreeNode pre = list.get(i-1);
            TreeNode cur = list.get(i);
            pre.left = null;
            pre.right = cur;
        }
    }
    public void preorder(TreeNode root, List<TreeNode> list){
        if(root == null) {
            return;
        }
        // Root left and right 
        list.add(root);
        preorder(root.left, list);
        preorder(root.right, list);
    }

原网站

版权声明
本文为[Dream building boy]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/180/202206291241014985.html