Traversal of binary trees

Recursive:

void traverse (TreeNode root) { if (root == null) { return null; } // forward traverse(root.left); // middle sequence traverse(root.right); }}Copy the code

Data structures and algorithms

Antecedent non-recursive:

public static List<Integer> preOrder(TreeNode root) {
    if (root == null) {
        return null;
    }

    List<Integer> res = new LinkedList<>();
    Deque<TreeNode> stack = new LinkedList<>();
    stack.push(root); while (! stack.isEmptyTreeNode node = stack ().pop(a); res.add(node.val); // The printing order is: root left to right, so the right child is pushed if (node) first.right! = null) { stack.push(node.right);
        }

        if (node.left! = null) { stack.push(node.left);
        }

    }

    return res;
}
94. Middle order traversal of binary tree #Copy the code

Middle-order non-recursion:

public static List<Integer> infixOrder(TreeNode root) { if (root == null) { return null; } List<Integer> res = new LinkedList<>(); TreeNode temp = root; Deque<TreeNode> stack = new LinkedList<>(); while (temp ! = null || ! stack.isEmpty()) { while (temp ! = null) { stack.push(temp); // Add to stack temp = temp.left; } temp = stack.pop(a); // Access the top element res.add(temp.val);

         temp = temp.right; // The next element to be traversed is the leftmost node of the right subtree of temp. }Copy the code

Postordered non-recursive:

Public static List<Integer> public static List<Integer>postOrder(TreeNode root) {
    if (root == null) {
        return null;
    }

    LinkedList<Integer> res = new LinkedList<>();
    Deque<TreeNode> stack = new LinkedList<>();
    stack.push(root); while (! stack.isEmpty()) {
        TreeNode temp = stack.pop(a); // If you add the root to the end, the output will be the reverse of the root to the right and left.addFirst(temp.val);

        if (temp.left! = null) { stack.push(temp.left);
        }

        if (temp.right! = null) { stack.push(temp.right);
        }
    }

    return res;
}
Copy the code

Note: If the non-recursive solution is difficult to understand, you can first follow the above code with the example of hand push. The important thing is to form the template and memorize it first, and then do it a few more times to understand it slowly.

Given a binary tree, return the values of nodes traversed in order. (That is, layer by layer, all nodes are accessed from left to right).

/** * 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 List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new LinkedList<>(); if (root == null) { return res; } Deque<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (! queue.isEmptyInt size = queue.size(a); List<Integer> rowList = new LinkedList<>(); For (int) select first in first out (left to right) from first in first out (left to right)i = 0; i < size; i++) {
                TreeNode node = queue.poll(a); rowList.add(node.val);

                if (node.left! = null) { queue.offer(node.left);
                }

                if (node.right! = null) { queue.offer(node.right);
                }
            }
			
            res.add(rowList); } return res; }}Copy the code

Given a binary tree, find its maximum depth.

The depth of a binary tree is the number of nodes along the longest path from the root node to the farthest leaf node.

lass Solution {
    /** * definition: * returns the maximum depth at root */Public int maxDepth(TreeNode root) {// Base case, root is empty if the tree height is0If (root == null) {return0;
        }

        /** * By definition, the maximum depth of the tree for root nodes is: * the maximum depth of the left and right subtrees + 1 */
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);

        return 1 + Math.max(left.right); }}Copy the code
  • Many of the problems related to binary trees evolved from three recursive traversals of binary trees
  • In order to know the maximum depth of the current binary tree, we need to know the maximum depth of the two subtrees. Therefore, we use the backward traversal (bottom up).
  • Do not use your head to simulate a recursive stack when writing a recursive program. After the function is defined, write code according to the definition

Given a binary tree, determine whether it is a highly balanced binary tree.

Class Solution {private Boolean balance = true; public boolean isBalanced(TreeNode root) {height(root); return balance; } // Get the height of two subtrees from bottom to top, and check whether the height difference between left and right subtrees is less than or equal to1
    private int height(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int left = height(root.left);
        int right = height(root.right);

        if (Math.abs(left - right) > 1) {
            balance = false;
        }

        return Math.max(left.right) + 1; }}Copy the code

A path is defined as a sequence that starts at any node in the tree and follows parent to child nodes to reach any node. The same node appears at most once in a path sequence. The path contains at least one node and does not necessarily go through the root node.

Path and is the sum of the values of all nodes in a path.

Give you the root node of a binary tree, root, return its maximum path and.

/** * 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 maxPathSum(TreeNode root) { maxSumToDescendant(root); return maxPathSum; } private int maxPathSum = Integer.MIN_VALUE; // Function definition: Private int maxSumToDescendant(TreeNode root) {if (root == null) {return0; } / / less than0Is considered to contribute int to the maximum path andleft = Math.max(0, maxSumToDescendant(root.left));
        int right = Math.max(0, maxSumToDescendant(root.right)); MaxPathSum = Math maxPathSum = Math maxPathSum = Math maxPathSum = Math.max(maxPathSum, left + root.val + right);

        return root.val + Math.max(left.right); }}Copy the code

Given a binary tree, find the nearest common ancestor of the two specified nodes in the tree.

If one node is found, it will return from bottom to top. If P and Q are not nodes in the opposite subtree, p and Q will finally meet at a node, and this node is the nearest common ancestor. Otherwise p or Q is the nearest common node.

Class Solution {//p! =q
    //     p 和 qAll exist in a given binary tree. public TreeNode lowestCommonAncestor(TreeNode root, TreeNodep, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }

        TreeNode left = lowestCommonAncestor(root.left.p.q);
        TreeNode right = lowestCommonAncestor(root.right.p.q);

        if (left! = null &&right! = null) { return root; } returnleft! = null ?left: right; }}Copy the code

Given a binary tree, return a bottom-up traversal of its node values. (that is, from the layer where the leaf node is located to the layer where the root node is located, layer by layer from left to right)

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        LinkedList<List<Integer>> res = new LinkedList<>();
        if (root == null) {
            return res;
        }

        Deque<TreeNode> queue = new LinkedList<>();
        queue.offerLast(root); while (! queue.isEmpty() {// Get the number of nodes in the current layer int size = queue.size(a); List<Integer> tempList = new LinkedList<>(); TreeNode tempNode; for (inti = 0; i < size; i++) {
                tempNode = queue.poll(a); tempList.add(tempNode.val);

                if (tempNode.left! = null) { queue.offer(tempNode.left);
                }

                if (tempNode.right! = null) { queue.offer(tempNode.right); }} // Place the results of each layer in reverse order into the final list res.addFirst(tempList); } return res; }}Copy the code

Given a binary tree, return a zigzag sequence traversal of its node values. (that is, the next layer is traversed from left to right, then right to left, and so on, alternating between layers).

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new LinkedList<>();
        if (root == null) {
            return res;
        }

        Deque<TreeNode> queue = new LinkedList<>();
        queue.offerLast(root); boolean flag = true; while(! queue.isEmpty() {// Get the number of nodes in the current layer int size = queue.size(a); LinkedList<Integer> tempList = new LinkedList<>(); TreeNode tempNode; for (inti = 0; i < size; i++) {
                tempNode = queue.pollFirst(a); If (flag == true) {// Store tempList from front to back.addLast(tempNode.val); } else {// Store tempList backwards from front to back.addFirst(tempNode.val);
                }

                if (tempNode.left! = null) { queue.offerLast(tempNode.left);
                }

                if (tempNode.right! = null) { queue.offerLast(tempNode.right);
                }
            }

            res.add(tempList); Flag flag =! flag; } return res; }}Copy the code

Binary search tree

Given a binary tree, determine whether it is a valid binary search tree.

Suppose a binary search tree has the following characteristics:

  • The left subtree of a node contains only numbers less than the current node.

  • The right subtree of a node only contains numbers greater than the current node.

  • All left and right subtrees must themselves also be binary search trees.

/** * 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 isValidBST(TreeNode root) { return isValidBST(root, null, null); } // define whether the binary tree whose current node is the root is a binary search tree. Each node of a binary search tree has an upper and lower bound (except the root node) private Boolean isValidBST(TreeNode node, TreeNode Low, TreeNode high) { //base case if (node == null) { return true; } //base case, the current node is less than or equal to the lower bound or greater than or equal to the upper bound of the binary search tree. = null && node.val <= low.val) return false; if (high ! = null && node.val >= high.val) return false;

        boolean ret = isValidBST(node.left, low, node) && isValidBST(node.right, node, high); return ret; }}Copy the code

Insert operations in binary search trees

Inserts the value into the binary search tree (BST) given the root node and the value in the tree to be inserted. Returns the root node of the inserted binary search tree. The input data guarantees that the new value is different from any node in the original binary search tree.

Note that there may be several effective ways to insert, as long as the tree remains a binary search tree after insertion. You can return any valid result.

Class Solution {// define: Public TreeNode insertIntoBST(TreeNode root, TreeNode insertIntoBST) int val) { if (root == null) { return new TreeNode(val); } // Be sure to write recursive code by definition if (root).val> val) {// if val is less than the value of the current node, the left subtree root is inserted.left = insertIntoBST(root.left, val);
        } else {
            root.right = insertIntoBST(root.right, val); } return root; }}Copy the code

Delete a node in the binary search tree

Given the root node of a binary search tree root and a value of key, delete the nodes corresponding to key in the binary search tree and ensure that the properties of the binary search tree remain unchanged. Returns a reference to the root node of the binary search tree (which may be updated).

In general, node deletion can be divided into two steps:

1. Locate the node to be deleted. 2. If found, delete it.

Note: The algorithm time complexity is O(h), h is the height of the tree.

Class Solution {// define: Public TreeNode deleteNode(TreeNode root, TreeNode root, int key) { // base case if (root == null) { return root; } // Remember to write recursive code by definition if (root).val== key) {//base case, delete the node is a leaf or just a non-leaf with a subtree if (root).left == null) return root.right;
            if (root.right == null) return root.left; TreeNode node = getMin(root) TreeNode node = getMin(root).right);
            root.val = node.val;

            root.right = deleteNode(root.right, node.val); } else if (root).val < key) {
            root.right = deleteNode(root.right, key);
        } else if (root.val > key){
            root.left = deleteNode(root.left, key); } return root; } private TreeNode getMin(TreeNode root) {while(root)} private TreeNode getMin(TreeNode root).left! = null) { root = root.left; } return root; }}Copy the code

The article is reprinted with music bytes