Advanced application of binary tree

One 、 Advanced application of binary tree

1. The binary tree traverses by layer and collects nodes

Leetcode The original title is https://leetcode.cn/problems/binary-tree-level-order-traversal-ii

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

//  Test link ：https://leetcode.cn/problems/binary-tree-level-order-traversal-ii
public class BinaryTreeLevelOrderTraversalII {
    

    public static class TreeNode {
    
        public int val;
        public TreeNode left;
        public TreeNode right;

        TreeNode(int val) {
    
            this.val = val;
        }
    }

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
    
        List<List<Integer>> ans = new LinkedList<>();
        if (root == null) {
    
            return ans;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
    
            int size = queue.size();
            List<Integer> curAns = new LinkedList<>();
            for (int i = 0; i < size; i++) {
    
                TreeNode curNode = queue.poll();
                curAns.add(curNode.val);
                if (curNode.left != null) {
    
                    queue.add(curNode.left);
                }
                if (curNode.right != null) {
    
                    queue.add(curNode.right);
                }
            }
            ans.add(0, curAns);
        }
        return ans;
    }
}

2. Determine if it's a balanced binary tree

Leetcode The original title is https://leetcode.cn/problems/balanced-binary-tree

//  Test link ：https://leetcode.cn/problems/balanced-binary-tree
public class BalancedBinaryTree {
    

    public static class TreeNode {
    
        public int val;
        public TreeNode left;
        public TreeNode right;

        TreeNode(int val) {
    
            this.val = val;
        }
    }

    public static class Info {
    
        public boolean isBalanced;
        public int height;

        public Info(boolean i, int h) {
    
            isBalanced = i;
            height = h;
        }
    }

    public static boolean isBalanced(TreeNode root) {
    
        return process(root).isBalanced;
    }

    public static Info process(TreeNode root) {
    
        if (root == null) {
    
            return new Info(true, 0);
        }
        Info leftInfo = process(root.left);
        Info rightInfo = process(root.right);
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        boolean isBalanced = leftInfo.isBalanced && rightInfo.isBalanced
            && Math.abs(leftInfo.height - rightInfo.height) < 2;
        return new Info(isBalanced, height);
    }

}

3. Whether the path and

Leetcode The original title is https://leetcode.cn/problems/path-sum

//  Test link ：https://leetcode.cn/problems/path-sum
public class Code03_PathSum {
    

   public static class TreeNode {
    
      public int val;
      public TreeNode left;
      public TreeNode right;

      TreeNode(int val) {
    
         this.val = val;
      }
   }

   public static boolean isSum = false;

   public static boolean hasPathSum(TreeNode root, int sum) {
    
      if (root == null) {
    
         return false;
      }
      isSum = false;
      process(root, 0, sum);
      return isSum;
   }

   public static void process(TreeNode x, int preSum, int sum) {
    
      if (x.left == null && x.right == null) {
    
         if (x.val + preSum == sum) {
    
            isSum = true;
         }
         return;
      }
      // x Is a non leaf node 
      preSum += x.val;
      if (x.left != null) {
    
         process(x.left, preSum, sum);
      }
      if (x.right != null) {
    
         process(x.right, preSum, sum);
      }
   }

   public static boolean hasPathSum2(TreeNode root, int sum) {
    
      if (root == null) {
    
         return false;
      }
      return process(root, sum);
   }

   public static boolean process(TreeNode root, int rest) {
    
      if (root.left == null && root.right == null) {
    
         return root.val == rest;
      }
      boolean ans = root.left != null && process(root.left, rest - root.val);
      ans |= root.right != null && process(root.right, rest - root.val);
      return ans;
   }

}

4. Collect compliance paths and

Leetcode The original title is https://leetcode.cn/problems/path-sum-ii

import java.util.ArrayList;
import java.util.List;

//  Test link ：https://leetcode.cn/problems/path-sum-ii
public class PathSumII {
    

    public static class TreeNode {
    
        public int val;
        public TreeNode left;
        public TreeNode right;

        TreeNode(int val) {
    
            this.val = val;
        }
    }

    public List<List<Integer>> pathSum(TreeNode head, int targetSum) {
    
        List<List<Integer>> lists = new ArrayList<>();
        if (head == null) return lists;
        process(head, targetSum, new ArrayList<>(), lists);
        return lists;
    }

    public void process(TreeNode head, int target, List<Integer> list, List<List<Integer>> lists) {
    
        if (head.left == null && head.right == null) {
    
            if (target == head.val) {
    
                list.add(head.val);
                ArrayList<Integer> temp = new ArrayList<>(list);
                lists.add(temp);
                list.remove(list.size() - 1);
            }
            return;
        }
        list.add(head.val);
        if (head.left != null) {
    
            process(head.left, target - head.val, list, lists);
        }
        if (head.right != null) {
    
            process(head.right, target - head.val, list, lists);
        }
        list.remove(list.size() - 1);
    }

}

5. Determine if it's a search Binary Tree

Leetcode The original title is https://leetcode.cn/problems/validate-binary-search-tree/submissions/

//  Test link ：https://leetcode.cn/problems/validate-binary-search-tree/submissions/
public class IsBinarySearchTree {
    

    public static class TreeNode {
    
        public int val;
        public TreeNode left;
        public TreeNode right;

        TreeNode(int val) {
    
            this.val = val;
        }
    }

    public static class Info {
    
        public boolean isBST;
        public int max;
        public int min;

        public Info(boolean is, int ma, int mi) {
    
            isBST = is;
            max = ma;
            min = mi;
        }
    }

    public static Info process(TreeNode x) {
    
        if (x == null) {
    
            return null;
        }
        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);
        int max = x.val;
        int min = x.val;
        if (leftInfo != null) {
    
            max = Math.max(leftInfo.max, max);
            min = Math.min(leftInfo.min, min);
        }
        if (rightInfo != null) {
    
            max = Math.max(rightInfo.max, max);
            min = Math.min(rightInfo.min, min);
        }
        boolean isValidBST = (leftInfo == null || leftInfo.isValidBST) && (rightInfo == null || rightInfo.isValidBST);
        if (!isValidBST) {
    
            return new Info(isValidBST, max, min);
        }
        isValidBST = (leftInfo == null || leftInfo.max < head.val) && (rightInfo == null || rightInfo.min > head.val);
        return new Info(isBST, max, min);
    }

}

Two 、 Written in the back

Welcome to your attention , Will often record some problems encountered in algorithm learning .

Please feel free to leave a message to discuss , Let me share with you , Know all but answer ！