算法

树

树结构相关的算法

 

遍历

递归

public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result=new ArrayList<>();
        sort(result,root);
        return result;
    }
private void sort(List<Integer> result,TreeNode node){
        if(node!=null){
            result.add(node.val);
            sort(result,node.left);
            sort(result,node.right);
        }
}

迭代

不同于遍历的规整，三种顺序的迭代逻辑各不相同。

/**
     * 迭代-前序
     * 中-左-右 借用栈来压入，首先压入根节点，之后弹出栈顶的节点，并按照右孩子-左孩子的顺序压入，并记录当前节点的值。
     * @param root
     * @return
     */
    public List<Integer> preorderTraversalIterator(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            result.add(node.val);
            if (node.right != null) {
                stack.push(node.right);
            }
            if (node.left != null) {
                stack.push(node.left);
            }
        }
        return result;
    }

    /**
     * 迭代-中序
     * 中序的思想是，左-中-右，因此可以先将整个左子树全部压入栈中，直到到达最左下角的叶子节点，输出当前节点并把右孩子压入栈中
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            result.add(root.val);
            root=root.right;
        }
        return result;
    }

    /**
     * 迭代-后序
     * 相对好理解的思路
     * 先搞左子树，左子树搞完，搞右子树，右子树搞完，添加root
     * @param root
     * @return
     */
    public static List<Integer> postorderTraversal(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> result = new ArrayList<>();
        HashSet<TreeNode> parent = new HashSet<>();
        while (root != null || !stack.isEmpty()) {
            if (root == null && parent.contains(stack.peek())) {
                //当左子树和右子树都处理完了
                result.add(stack.pop().val);
            } else if (root == null) {
                parent.add(stack.peek());
                //然后处理右子树
                root = stack.peek().right;
            } else {
                //先将左边的节点都放到队列
                stack.push(root);
                root = root.left;
            }
        }
        return result;
    }

层级遍历

public List<List<Integer>> levelOrder(TreeNode root) {

        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> temp = new ArrayList<>();
            int size = queue.size();
            while (size > 0) {
                TreeNode node = queue.poll();
                temp.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                size--;
            }
            result.add(temp);
        }
        return result;
    }

填充每个节点的下一个右侧节点指针

116. 填充每个节点的下一个右侧节点指针

//本质上依然是层级遍历
public Node connect(Node root) {
        if (root == null) {
            return root;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            Node right=null;
            while (size > 0) {
                Node node = queue.poll();
                node.next=right;
                right=node;
                if (node.right != null) {
                    queue.offer(node.right);
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                size--;
            }
        }
        return root;
    }

二叉树的最大最小深度

/**
     * 二叉树的最大深度
     * 也可以使用层级遍历来记录
     * @param root
     * @return
     */
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
    }

    /**
     * 二叉树的最小深度
     * @param root
     * @return
     */
    public int minDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = minDepth(root.left);
        int right = minDepth(root.right);
        // 如果左子树或者右子树为0，那得以不为空的那棵树为准
        if (left == 0 || right == 0) {
            return left + right + 1;
        }
        return Math.min(left, right) + 1;
    }

填充每个节点的下一个右侧指针节点

116. 填充每个节点的下一个右侧节点指针

public Node connect(Node root) {
        if (root == null) {
            return root;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            Node right=null;
            while (size > 0) {
                Node node = queue.poll();
                node.next=right;
                right=node;
                if (node.right != null) {
                    queue.offer(node.right);
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                size--;
            }
        }
        return root;
    }

平衡二叉树

110. 平衡二叉树

    public boolean isBalanced(TreeNode root) {
        if(root==null){
            return true;
        }
        if(Math.abs(depth(root.left)-depth(root.right))>1){
            return false;
        }
        return isBalanced(root.left)&&isBalanced(root.right);
    }
    public int depth(TreeNode root){
        if(root==null){
            return 0;
        }
        return Math.max(depth(root.left),depth(root.right))+1;
    }

从中序和后序构造二叉树

106. 从中序与后序遍历序列构造二叉树

public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (postorder.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[postorder.length - 1]);
        if (postorder.length == 1) {
            return root;
        }
        int index = findIndex(inorder, root.val);
        root.left = buildTree(
                Arrays.copyOfRange(inorder, 0, index),
                Arrays.copyOfRange(postorder, 0, index));
        root.right = buildTree(
                Arrays.copyOfRange(inorder, index + 1, inorder.length),
                Arrays.copyOfRange(postorder, index, postorder.length-1));
        return root;
    }

    private int findIndex(int[] inorder, int target) {
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == target) {
                return i;
            }
        }
        return -1;
    }

验证二叉搜索树

98. 验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

  • 节点的左子树只包含 小于 当前节点的数。

  • 节点的右子树只包含 大于 当前节点的数。

  • 所有左子树和右子树自身必须也是二叉搜索树。

思路：

  1. 中序遍历看是否有序。

  2. 递归：递归的话其实也是中序的思想，单个节点要大于前面的节点，小于后面的节点，因此，由上到下，缩小区间，节点只需要和区间比较即可

/**
     * 是否是有效的二叉搜索树
     * @param root
     * @return
     */
    public static boolean isValidBST(TreeNode root) {
        return isValidBST(root,Long.MIN_VALUE,Long.MAX_VALUE);
    }
    public static boolean isValidBST(TreeNode node,Long min,Long max){
        if(node==null){
            return true;
        }
        if(node.val<=min||node.val>=max){
            return false;
        }
        return isValidBST(node.left,min,Long.valueOf(node.val))&&isValidBST(node.right,Long.valueOf(node.val),max);
    }

二叉搜索树中的众数

501. 二叉搜索树中的众数

/**
 * 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 {
    int cur , count = 0, max = 0;
    List<Integer> result = new ArrayList<>();

    public int[] findMode(TreeNode root) {
        dfs(root);
        int[] arr = new int[result.size()];
        for (int i = 0; i < result.size(); i++) {
            arr[i] = result.get(i);
        }
        return arr;
    }

    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        if (root.val==cur) {
            count++;
        }else {
            cur = root.val;
            count = 1;
        }
        if (count == max) {
            result.add(cur);
        } else if (count > max) {
            max = count;
            result.clear();
            result.add(cur);
        }
        dfs(root.right);
    }
}

最近公共祖先

236. 二叉树的最近公共祖先

//普通二叉树
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null||root==q||root==p){
            return root;
        }
        //在左子树能否找到
        TreeNode left=lowestCommonAncestor(root.left,p,q);
        TreeNode right=lowestCommonAncestor(root.right,p,q);
        if(left==null&&right==null){
            return null;
        //如果左边找不到，那么就代表两个节点一定在右子树，此时最先遇到的节点就是祖先
        }else if(left==null){
            return right;
        }else if(right==null){
            return left;
        }else{
        //如果左边也有，右边也有，那当前节点肯定就是最近祖先了
            return root;
        }
    }
//二叉搜索树
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root.val>p.val&&root.val>q.val){
           return lowestCommonAncestor(root.left,p,q);
        }else if(root.val<p.val&&root.val<q.val){
            return lowestCommonAncestor(root.right,p,q);
        }else{
            return root;
        }
    }

删除二叉搜索树的节点

450. 删除二叉搜索树中的节点

public TreeNode deleteNode(TreeNode root, int key) {
        if(root==null){
            return null;
        }
        if (root.val == key) {
            //左右任意节点为空，返回不为空的
            if (root.left == null || root.right == null) {
                return root.left == null ? root.right : root.left;
            }else{
            //左右节点都不为空，将左节点置为右节点的左节点
                TreeNode cur=root.right;
                while(cur.left!=null){
                    cur=cur.left;
                }
                cur.left=root.left;
                return root.right;
            }
        } else if (root.val > key) {
            root.left = deleteNode(root.left, key);
        } else {
            root.right = deleteNode(root.right, key);
        }
        return root;
    }

修建二叉树

669. 修剪二叉搜索树

给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在 唯一的答案 。

public TreeNode trimBST(TreeNode root, int low, int high) {
        if(root==null){
            return null;
        }
        if(root.val==low){
            root.left=null;
        }else if(root.val<low){
         return trimBST(root.right,low,high);
        }
        if(root.val==high){
            root.right=null;
        }else if(root.val>high){
         return trimBST(root.left,low,high);
        }
        root.left=trimBST(root.left,low,high);
        root.right=trimBST(root.right,low,high);
        return root;
    }

恢复二叉搜索树

99. 恢复二叉搜索树

思路：

中序遍历+找到错误节点

区分错误节点是1个和2个的情况

class Solution {
    TreeNode prev,next;
    List<TreeNode> errorNode=new ArrayList<>();
    public void recoverTree(TreeNode root) {
        dfs(root);
        if(errorNode.size()>1){
            next=errorNode.get(1);
        }
        int temp=errorNode.get(0).val;
        errorNode.get(0).val=next.val;
        next.val=temp;
    }
    private void dfs(TreeNode root){
        if(root==null){
            return ;
        }
        dfs(root.left);
        //1,2,6,4,5,3,7,8
        if(prev!=null&&root.val<prev.val){
            //如果是第一次遇到错误的节点，那么需要将prev和next都要记录下来，即6和4都要记录下来
            //这样如果正好是这两个，交换即可
            if(errorNode.size()==0){
                errorNode.add(prev);
                next=root;
            }else{
                //如果第二次遇到错误节点，即证明是这个节点和前一个errorNode交换
                errorNode.add(root);
            }

        }
        prev=root;
        dfs(root.right);
    }
}
Licensed under CC BY-NC-SA 4.0
最后更新于 2024-10-18