Leetcode 05 tree

character string

Basic knowledge of

Definitions and related concepts

1. Linked list and graph

Single chain list ： A data field + A pointer field

Trees ： A data field + Multiple pointer fields

chart ： Vertex set + edge

Trees ： Acyclic connected graph , Is a special kind of graph .

2. The definition of a tree

Trees are N（N>=0） A finite set of nodes .N=0 Time is an empty tree ,N>0 The following requirements shall be met when ：

• There is and only one specific node called the root
• N>1 when , The rest of the nodes can be divided into m(m>0) A finite set of disjoint . Each finite set is itself a tree

3. The concept of trees ：

• The root node ： The node at the top of the non empty tree , The rest of the nodes are its descendants
• Degree of node ： The number of child nodes a node has
• Leaf node ： Degree is 0 The node of
• Parent child nodes ： A pair of directly connected nodes , At the top is the parent node , At the lower level are child nodes
• Brother node ： Different nodes generated by the same parent node are called brother nodes
• Node hierarchy ： Start with the root and write it as 1 layer , Its child nodes are 2 layer , The grandson node is 3 layer
• Node depth ： The number of layers where the node is located
• Depth of tree / Height ： Number of maximum layers
• Node height ： The depth of the subtree with the node as the root / Height
• Ordered trees ： The new tree obtained by exchanging the position of the subtree whose brother node is the root is regarded as a tree different from the original tree
• Disordered trees ： The new tree obtained by exchanging the position of the subtree whose brother node is the root is regarded as the same tree as the original tree

4. Special trees

• Binary tree ： A binary tree is one in which the degree of each node is not greater than 2 The tree of , And the binary tree is an ordered tree
• Full binary tree ： All leaf nodes are at the bottom , And all non leaf node degrees are 2, It must be a complete binary tree
• Perfect binary tree ： The leaf nodes at the bottom layer are closely arranged from left to right
• Binary search tree ： Or it's an empty tree , Either all the node keywords of the left subtree are smaller than the root node keywords , All node keywords of the right subtree are greater than the root node keywords , And the left and right subtrees are binary search trees .
• Balanced binary trees （AVL）： If the height difference between the left and right subtrees of each node in the binary tree is not greater than 1, It's a balanced binary tree , Generally, it is combined with binary search tree to form a balanced binary search tree , Used to find data .

The basic operation of trees

1. The storage structure of the tree

• Sequential storage structure ： Graphs can be represented by adjacency tables , The tree uses adjacency tables with parent nodes , That is, parent-child node representation , And the parent node representation 、 Child node representation
• Chain storage structure ： Use a linked list to represent a node and its child nodes

2. The addition, deletion, modification and search of trees

In the addition, deletion and modification of the tree , lookup / Search for / Traversal is a tree The core operation .

3. Inquire about

Traverse ： According to some rules “ visit ” Every node in the tree , Ensure that every node will be “ visit ” To and each node is only “ visit ” once

“ visit ”： The program interacts with the node or performs some operations on the node

“ Get into ”： The program comes to a node , There is no interaction with this node

Under different rules , For the same node “ Get into ” There may be one or more times , But for the same node “ visit ” Only once .

• Depth first search of binary tree DFS

You can find that every node has “ Get into ” Three times , According to the node “ Get into ” In the order of , For the first time “ Get into ” visit 、 The second time “ Get into ” visit 、 third time “ visit ” The traversal of the tree can be divided into the first root （ order ） Traverse 、 Nakagan （ order ） Traversal and post root （ order ） Traverse .

def dfs(TreeNode root):
    if not root:
        return
    # print(root.val) #  The first sequence traversal 
    dfs(root.left)
    # print(root.val) #  In the sequence traversal 
    dfs(root.right)
    # print(root.val) #  After the sequence traversal 

• Breadth first search BFS： Start at the root node , From top to bottom , From left to right in the same level “ visit ” Every node , Also called hierarchical traversal , Each node will only ” Get into “ once .

def bfs(self, root: Optional[TreeNode]):
	q = []
    q.append(root)
    while len(q) and q[0]:
        cur = q.pop()
        print(cur.val)
        if root.left:
            q.append(root.left)
        if root.right:
            a.append(root.right)
    return 


def bfs(self, root: Optional[TreeNode]):
	q = []
    q.append(root)
    while len(q) and q[0]:
        for i in range(len(q)):
            cur = q.pop()
            print(cur.val)
            if root.left:
                q.append(root.left)
            if root.right:
                a.append(root.right)

title

The maximum depth of a binary tree

1. Title Description

Topic link

2. Analysis idea and code

• recursive ： For each node , Its maximum depth is equal to the maximum of its left subtree depth and right subtree depth plus 1
• Breadth first search ： Is to add... To the breadth first search template 1 that will do

	public int maxDepth(TreeNode root) {
    
        if (root == null)   return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }


	public int maxDepth(TreeNode root) {
    
        if (root == null)   return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        
        queue.offer(root);
        int ans = 0;
        while (!queue.isEmpty()) {
    
            int size = queue.size();
            ans ++ ;
            for (int i = 0; i < size; i ++ ) {
    
                TreeNode node = queue.poll();
                if (node.left != null)  queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
        return ans;
    }

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

Convert an ordered array to a binary search tree

1. Title Description

Topic link

2. Solution ideas and code

Ideas ：

Recursively construct , Select the middle value of the array as the root node of the current subtree

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
class Solution {
    
    public TreeNode sortedArrayToBST(int[] nums) {
    
        return helper(nums, 0, nums.length - 1);
    }
    
    public TreeNode helper(int[] nums, int l, int r) {
    
        if (l > r)  return null;
        
        int mid = l + (r - l) / 2;
        
        TreeNode root = new TreeNode(nums[mid]);
        root.left = helper(nums, l, mid - 1);
        root.right = helper(nums, mid + 1, r);
        return root;
    }
}

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        def helper(l, r):
            if l > r:
                return None
            mid = int(l + (r - l) / 2)
            root = TreeNode(nums[mid])
            root.left = helper(l, mid - 1)
            root.right = helper(mid + 1, r)
            return root
        return helper(0, len(nums) - 1)

Minimum depth of binary tree

1. Title Description

Topic link

2. Solution ideas and code

Recursive solution , Turn big problems into sub problems , If the current node is empty , return 0, The left and right nodes of the current node are empty , return 1, The left node of the current node is not empty , Calculate the minimum depth of the left node , The right node of the current node is not empty , Calculate the minimum depth of the right node , Finally, the minimum depth is returned +1 that will do .

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
class Solution {
    
    public int minDepth(TreeNode root) {
    
        if (root == null)   return 0;
        
        if (root.left == null && root.right == null)    return 1;
        int min_depth = Integer.MAX_VALUE;
        if (root.left != null)  min_depth = Math.min(min_depth, minDepth(root.left));
        
        if (root.right != null) min_depth = Math.min(min_depth, minDepth(root.right));
        
        return min_depth + 1;
        
    }

}

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
    def minDepth(self, root: TreeNode) -> int:
        if not root:
            return 0
        if not root.left and not root.right:
            return 1
        min_depth = 10**9
        if root.left:
            min_depth = min(self.minDepth(root.left), min_depth)
        if root.right:
            min_depth = min(self.minDepth(root.right), min_depth)
        return min_depth + 1

The sum of the paths

1. Title Description

Topic link

2. Solution ideas and code

Also use recursion to solve , Turn big problems into small ones , If the current node is empty , return false, If the left node and the right node of the current node are empty, the current sum plus the current node value is returned targetSum equal , Otherwise, judge whether the sum of the left subtree or the sum of the right subtree plus the current node value is equal to targetSum.

Optimize ： In the above methods , For each node, you need to save three pieces of information ： Current node 、 The present and 、 Objectives and , It can be optimized , Convert the path sum of the solution tree into the sum of the left subtree or the right subtree targetSum - root.val Value .

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
class Solution {
    
    public boolean hasPathSum(TreeNode root, int targetSum) {
    
        return helper(root, 0, targetSum);
    }
    
    public boolean helper(TreeNode root, int sum, int targetSum) {
    
        if (root == null)   return false;
        if (root.left == null && root.right == null)    return sum + root.val == targetSum;
        return helper(root.left, sum + root.val, targetSum) || helper(root.right, sum + root.val, targetSum);
    }
}

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:
            return False
        if not root.left and not root.right:
            return targetSum == root.val
        return self.hasPathSum(root.left, targetSum - root.val) or self.hasPathSum(root.right, targetSum - root.val)

Binary search tree iterator

1. Title Description

Topic link

2. Solution ideas and code

• Save the middle order traversal results to the array in advance , Then operate on the array
• Use the stack to maintain the middle order traversal of the binary tree , Real time maintenance stack .

/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */
class BSTIterator {
    
    private TreeNode cur;
    private Deque<TreeNode> stack;

    public BSTIterator(TreeNode root) {
    
        cur = root;
        stack = new LinkedList<>();
    }
    
    public int next() {
    
        while (cur != null) {
    
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        int res = cur.val;
        cur = cur.right;
        return res;
    }
    
    public boolean hasNext() {
    
        return cur != null || !stack.isEmpty();
    }
}

/** * Your BSTIterator object will be instantiated and called as such: * BSTIterator obj = new BSTIterator(root); * int param_1 = obj.next(); * boolean param_2 = obj.hasNext(); */

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class BSTIterator:

    def __init__(self, root: TreeNode):
        def inorder(root, res):
            if not root:
                return
            inorder(root.left, res)
            res.append(root.val)
            inorder(root.right, res)
        self.arr = list()
        inorder(root, self.arr)
        self.idx = 0
        
    def next(self) -> int:
        res = int(self.arr[self.idx])
        self.idx += 1
        return res

    def hasNext(self) -> bool:
        return self.idx < len(self.arr)


# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()