二叉树

二叉树的中序遍历

• 左中右

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        inorder(root, result);
        return result;
    }

    private void inorder(TreeNode root, List<Integer> result) {
        if (root == null) {
            return;
        }
        inorder(root.left, result);
        result.add(root.val);
        inorder(root.right, result);
    }
}

验证BST

• 简单解法：中序遍历的结果放到一个新数组，看是不是单调递增，是的话就是BST
• 可以不用数组保存：
  • 用一个变量 prev 记录上一个访问过的节点的值
  • 每访问一个节点时，比较它的值是否比 prev 大（必须严格递增）
  • 如果发现不满足，直接返回 false
  • 如果遍历完所有节点都满足，则返回 true

class Solution {
    private long prev = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (!isValidBST(root.left)) {
            return false;
        }

        if (root.val <= prev) { // 遍历的前一个节点大于等于当前节点，无法满足BST。不能等于因为BST的节点值不能重复
            return false;
        }
        prev = root.val;

        return isValidBST(root.right);
    }
}

恢复BST

• BST刚好有两个节点被交换了，恢复BST
• 中序遍历的结果是单调递增的，所以如果发现两个节点不满足单调递增，就是被交换了
• 用两个变量记录这两个节点，然后交换它们的值

class Solution {
    private TreeNode prev = null;
    private TreeNode first = null;
    private TreeNode second = null;
    public void recoverTree(TreeNode root) {
        recover(root);
        if (first != null && second != null) {
            int temp = first.val;
            first.val = second.val;
            second.val = temp;
        }
    }

    private void recover(TreeNode root){
        if (root == null) return;
        recover(root.left);
        // 当前节点值小于前一个节点值，说明出错了（中序遍历应该是升序）
        if(prev!=null && root.val<prev.val){
            // 第一次发现逆序对，记录前一个较大节点为 first，当前较小为 second
            if(first==null){
                first = prev;
                second = root;
                // 第二次逆序对更新 second（例如：两个错位节点不相邻）
            } else{
                second = root;
            }
        }
        prev = root;
        recover(root.right);
    }
}

判断两颗二叉树是否相同

• 前序遍历 中左右

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) return false; // 一个为空，一个不为空，false
        if (p.val != q.val) return false; // 值不相等，false
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); // 递归判断左右子树
    }
}

判断两颗二叉树是否对称

• 前序遍历 中右左

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) return true;
        return preOrder(root.left, root.right);
    }
    private boolean preOrder(TreeNode left, TreeNode right){
        if (left == null && right == null) return true;
        if (left == null || right == null) return false;
        if(left.val != right.val) return false;
        return preOrder(left.left,right.right) && preOrder(left.right,right.left);
    }
}

二叉树层序遍历

• 广度优先遍历
• 需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑
• 每一层遍历完，需要将队列中的元素出队，并将其左右子节点入队

class Solution {
    public List<List<Integer>> resList = new ArrayList<List<Integer>>();
    public List<List<Integer>> levelOrder(TreeNode root) {
        bfs(root);
        return resList;
    }
    //BFS--迭代方式--借助队列
    public void bfs(TreeNode node) {
        if (node == null) return;
        Queue<TreeNode> que = new LinkedList<TreeNode>(); 
        que.offer(node); // 根节点入队

        while (!que.isEmpty()) {
            List<Integer> itemList = new ArrayList<Integer>(); // 记录每层的节点值
            int len = que.size(); // 记录每层的节点数

            while (len > 0) { // 遍历当前层节点
                TreeNode tmpNode = que.poll(); // 当前层节点出队
                itemList.add(tmpNode.val); // 记录当前层节点值

                if (tmpNode.left != null) que.offer(tmpNode.left); // 下一层左子节点入队
                if (tmpNode.right != null) que.offer(tmpNode.right); // 下一层右子节点入队
                len--; // 当前层节点数减1
            }
            resList.add(itemList); // 记录当前层节点值
        }
    }
}

二叉树的右视图

• BFS层序遍历，然后找到每层最后一个节点

class Solution {
    public List<Integer> resList = new ArrayList<>();
    public List<Integer> rightSideView(TreeNode root) {
        bfs(root);
        return resList;
    }
    public void bfs(TreeNode node){
        if (node == null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(node);
        while (!queue.isEmpty()){
            int len = queue.size();
            while (len > 0){
                TreeNode tmpNode = queue.poll();
                if (tmpNode.left != null) queue.offer(tmpNode.left);
                if (tmpNode.right != null) queue.offer(tmpNode.right);
                len--;
                if (len == 0) resList.add(tmpNode.val); // 当前层最后一个节点
            }
        }
    }
}

二叉树的最近公共祖先

• 自底向上查找就好了，这样就可以找到公共祖先了
• 后序遍历 左右中

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || root == p || root == q) return root; // 终止条件：遇到 null 或遇到 p/q 本身，直接返回

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left == null && right == null) { // 若未找到节点 p 或 q
            return null;
        }else if(left == null && right != null) { // 若找到一个节点 右子树
            return right;
        }else if(left != null && right == null) { // 若找到一个节点 左子树
            return left;
        }else { // 若找到两个节点
            return root;
        }
    }
}

二叉搜索树的最近公共祖先

• 利用BST的性质，左子树的值都小于根节点，右子树的值都大于根节点
• 如果p和q的值都小于根节点，则它们的公共祖先在左子树
• 如果p和q的值都大于根节点，则它们的公共祖先在右子树
• 如果p和q的值一个大于根节点，一个小于根节点，则它们的公共祖先就是根节点

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) return null;
        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;
        }
    }
}