二叉树

题目

226. 翻转二叉树

  1. class Solution {
  2.     public TreeNode invertTree(TreeNode root) {
  3.         // 对每一个节点都进行翻转就可以
  4.         // 叶子节点就返回
  5.         if(root == null) return root;
  6.         // 处理每次交换
  7.         TreeNode left = invertTree(root.left);
  8.         TreeNode right = invertTree(root.right);
  9.         root.left = right;
  10.         root.right = left;
  11.         return root;
  12.     }
  13. }

101. 对称二叉树

这个题目做了三遍了，每次都是写不好。

  1. class Solution {
  2.     public boolean isSymmetric(TreeNode root) {
  3.         if(root == null){
  4.             return true;
  5.         }
  6.         return cmp(root.left,root.right);
  7.     }
  9.     private boolean cmp(TreeNode node1,TreeNode node2){
  10.         if(node1 == null && node2 == null){
  11.             return true;
  12.         }
  13.         if(node1==null || node2 == null || node1.val != node2.val){
  14.             return false;
  15.         }
  16.         return cmp(node1.left,node2.right) && cmp(node1.right,node2.left);
  17.     }
  18. }

104. 二叉树的最大深度

class Solution {
    public int maxDepth(TreeNode root) {
        // 我能想到的就是层序遍历试一下吧
        if(root==null){
            return 0;
        }
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        int depth = 0;
        while(!que.isEmpty()){
            depth++;
            int len = que.size();
            while(len>0){
                TreeNode node = que.poll();
                if(node.left!=null){
                    que.offer(node.left);
                }
                if(node.right!=null){
                    que.offer(node.right);
                }
                len--;
            }
        }
        return depth;
    }
}

111. 二叉树的最小深度

class Solution {
    public int minDepth(TreeNode root) {
        //最小深度
        if(root==null) return 0;
        Queue<TreeNode> que = new LinkedList<>();
        que.offer(root);
        int depth = 0;
        while(!que.isEmpty()){
            int size = que.size();
            depth++;
            while(size>0){
                TreeNode node = que.poll();
                if(node.left==null && node.right==null){
                    return depth;
                }
                if(node.left!=null){
                    que.offer(node.left);
                }
                if(node.right!=null){
                    que.offer(node.right);
                }
                size--;
            }
        }
        return depth;
    }
}

222. 完全二叉树的节点个数


class Solution {
    public int countNodes(TreeNode root) {

        Queue<TreeNode> que = new LinkedList<>();

        if(root==null) return 0;
        que.offer(root);
        int cnt=1;
        while(!que.isEmpty()){
            int size = que.size();
            while(size>0){
                TreeNode node = que.poll();
                if(node.left!=null){
                    que.offer(node.left);
                    cnt++;
                }
                if(node.right!=null){
                    que.offer(node.right);
                    cnt++;
                }
                size--;
            }
        }
        return cnt;
    }
}

二刷:

class Solution {
    int count;
    public int countNodes(TreeNode root) {
        if(root==null) return 0;
         // 我想到的是直接遍历搜索
         count = 0;
         preOrder(root);
         return count;
    }
    void preOrder(TreeNode root){
        if(root==null) return;
        count++;
        preOrder(root.left);
        preOrder(root.right);
    }
}

110. 平衡二叉树

class Solution {

    private boolean balance = true;

    public boolean isBalanced(TreeNode root) {
        if(root == null) return true;
        dfs(root);
        return balance;
    }

    // 求树的高度
    private int depth(TreeNode root){
        if(root == null){
            return 0;
        }
        return (Math.max(depth(root.left),depth(root.right))+1);
    }

    private void dfs(TreeNode root){
        if(root == null || balance == false) return;
        int absDepth = Math.abs(depth(root.left) - depth(root.right));
        if(absDepth>1){
            balance =false;
        }
        dfs(root.left);
        dfs(root.right);
    }
}

257. 二叉树的所有路径(抄)

class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        getPaths(root,"",res);
        return res;

    }
    public void getPaths(TreeNode root,String path,List<String> res){
        if(root == null) return;
        //节点值加入当前路径
        StringBuffer onePath = new StringBuffer(path);
        onePath.append(Integer.toString(root.val));
        // 如果当前节点是叶子结点，将当前路径加入结果集
        if(root.left == null && root.right == null){
            res.add(onePath.toString());
        }else{
            // 当前节点不是叶子节点，继续遍历左右子树
            onePath.append("->");
            getPaths(root.left,onePath.toString(),res);
            getPaths(root.right,onePath.toString(),res);
        }
    }
}

404. 左叶子之和(抄)

这个思路真是绝了，我想到了用前序遍历，但是没有设置isLeft变量，操作起来还是有点麻烦的，原来设置这一个变量就解决了。

class Solution {
    int sum = 0;
    public int sumOfLeftLeaves(TreeNode root) {
        // 只计算左叶子的和
        preOrder(root,false);
        return sum;
    }
    void preOrder(TreeNode root,boolean isLeft){
        if(root == null) return;
        if(root.left== null && root.right == null && isLeft){
            sum+=root.val;
            return;
        }
        preOrder(root.left,true);
        preOrder(root.right,false);
    }
}

513. 找树左下角的值

class Solution {
    public int findBottomLeftValue(TreeNode root) {
        Queue<TreeNode> que = new LinkedList<>();
        int res = root.val;
        que.add(root);
        while(!que.isEmpty()){
            int len = que.size();
            // 这个element() 要记得用
            res = que.element().val;
            while(len>0){
                TreeNode node = que.remove();
                if(node.left!=null){
                    que.add(node.left);
                }
                if(node.right!=null){
                    que.add(node.right);
                }
                len--;
            }
        }
        return res;
    }
}

112. 路径总和（抄）

class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null) return false;
        if(root.left == null&& root.right ==null){
            return root.val == sum;
        }
        return hasPathSum(root.left,sum-root.val) || hasPathSum(root.right,sum-root.val);
    }
}

654. 最大二叉树（抄）

class Solution {
    public TreeNode constructMaximumBinaryTree(int[] nums) {

        return function1(nums,0,nums.length);

    }

    public TreeNode function1(int[] nums,int leftIndex,int rightIndex){

        if(rightIndex-leftIndex<1){
            return null;
        }
        if(rightIndex-leftIndex==1){
            return new TreeNode(nums[leftIndex]);
        }
        TreeNode node = new TreeNode();
        // 先找最大值和对应的下标
        int maxValue = 0;
        int maxValueIndex = 0;
        for(int i = leftIndex;i<rightIndex;i++){
            if(nums[i]>maxValue){
                maxValue = nums[i];
                maxValueIndex = i;
            }
        }
        node.val = maxValue;
        // 找左区间
        node.left = function1(nums,leftIndex,maxValueIndex);
        node.right = function1(nums,maxValueIndex+1,rightIndex);
        // 找右区间
        return node;
    }
}

617. 合并二叉树（抄）

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1==null) return root2;
        if(root2 == null) return root1;
        TreeNode root = new TreeNode();
        root.val = root1.val+root2.val;
        // 我自己写已经到了这一步了，但是没写下面的递归就看了答案
        // 下次注意，不可先看答案
        root.left = mergeTrees(root1.left,root2.left);
        root.right = mergeTrees(root1.right,root2.right);
        return root;
    }

}

700. 二叉搜索树中的搜索

class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        while(root!=null){
            if(root.val==val){
                return root;
            }else if(root.val<val){
                root = root.right;
            }else{
                root = root.left;
            }
        }
        return root;
    }
}

530. 二叉搜索树的最小绝对差

class Solution {
    // 记录上一个遍历的结点
    TreeNode pre;
    int result = Integer.MAX_VALUE;

    public int getMinimumDifference(TreeNode root) {
        if(root==null) return 0;
        traversal(root);
        return result;
    }
    public void traversal(TreeNode root){
        if(root==null) return;
        traversal(root.left);
        if(pre!=null){
            result = Math.min(result,root.val-pre.val);
        }
        pre = root;
        traversal(root.right);
    }
}

98. 验证二叉搜索树

我是想到了中序遍历，得到中序序列，然后记录一个中序排序后的red序列，来比对二者是否一致。
没有全AC，因为有相同的节点，这样也是一致。
没有必要弄那个res序列，直接判断中序序列是否严格递增就可以了。

// 错误代码
class Solution {
    public boolean isValidBST(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        inOrderTraversal(root,list);
        List<Integer> res = new ArrayList<>();
        for(int i : list){
            res.add(i);
        }
        Collections.sort(list);
        for(int i = 0;i<res.size();i++){
            if(list.get(i) != res.get(i)) return false;
        }
        return true;
    }
    public void inOrderTraversal(TreeNode root,List<Integer> list){
        if(root == null) return;
        inOrderTraversal(root.left,list);
        list.add(root.val);
        inOrderTraversal(root.right,list);
    }
}

// 修改后的正确的做法
class Solution {
    public boolean isValidBST(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        inOrderTraversal(root,list);
        for(int i = 1;i<list.size();i++){
            if(list.get(i)<=list.get(i-1)){
                return false;
            }
        }
        return true;
    }
    public void inOrderTraversal(TreeNode root,List<Integer> list){
        if(root == null) return;
        inOrderTraversal(root.left,list);
        list.add(root.val);
        inOrderTraversal(root.right,list);
    }
}

124. 二叉树中的最大路径和(困难)

完全不会做.
给个偷懒做法。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {
    private TreeNode root;
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        this.root = root;
        return null;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

501. 二叉搜索树中的众数（抄）

头大，等会再做这个题。

class Solution {
    ArrayList<Integer> resList;
    int maxCount;
    int count;
    TreeNode pre;

    public int[] findMode(TreeNode root) {
        resList = new ArrayList<>();
        maxCount = 0;
        count = 0;
        pre = null;
        inOrderTraversal(root);
        int[] res = new int[resList.size()];
        for(int i = 0;i<resList.size();i++){
            res[i] = resList.get(i);
        }
        return res;
    }

    public void inOrderTraversal(TreeNode root){
        if(root == null) return;
        inOrderTraversal(root.left);

        int rootValue = root.val;
        // 计数
        if(pre==null || rootValue != pre.val){
            count = 1;
        }else{
            count++;
        }
        // 更新结果以及最大值
        if(count > maxCount){
            resList.clear();
            resList.add(rootValue);
            maxCount = count;
        }else if(count == maxCount){
            resList.add(rootValue);
        }
        pre = root;
        inOrderTraversal(root.right);
    }
}

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

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

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

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root.val>p.val && root.val>q.val) return lowestCommonAncestor(root.left,p,q);
        if(root.val<p.val && root.val<q.val) return lowestCommonAncestor(root.right,p,q);
        return root;
    }
}

701. 二叉搜索树中的插入操作

class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        // 如果当前节点为空，也意味着val找到了合适的位置，此时创建节点直接返回。
        if(root == null){
            return new TreeNode(val);
        }
        if(root.val<val){
            root.right = insertIntoBST(root.right,val);
        }else if(root.val>val){
            root.left = insertIntoBST(root.left,val);
        }
        return root;
    }
}

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

class Solution {
    public TreeNode deleteNode(TreeNode root, int key) {
        root = delete(root,key);
        return root;
    }

    public TreeNode delete(TreeNode root,int key){
        // 没找到直接返回空
        if(root==null) return null;

        if(root.val>key){
            root.left = delete(root.left,key);
        }else if(root.val<key){
            root.right = delete(root.right,key);
        }else{
            // 找到的节点没有左子树，直接返回右子树
            if(root.left == null){
                return root.right;
            }
            // 找到的节点没有右子树，直接返回左子树
            if(root.right == null){
                return root.left;
            }
            // 找到的节点左右孩子都有
            // 将该节点的左子树作为右子树的最左节点的左孩子
            TreeNode tmp = root.right;
            while(tmp.left!=null){
                tmp = tmp.left;
            }
            tmp.left = root.left;
            return root.right;
        }
        return root;
    }
}

669. 修剪二叉搜索树

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if(root == null) return null;
        if(root.val<low) return trimBST(root.right,low,high);
        if(root.val>high) return trimBST(root.left,low,high);
        // root 在[low,high]范围内
        root.left = trimBST(root.left,low,high);
        root.right = trimBST(root.right,low,high);
        return root;
    }
}

108. 将有序数组转换为二叉搜索树

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return sortedArrayToBST(nums, 0, nums.length);
    }
    public TreeNode sortedArrayToBST(int[] nums,int left,int right){
        if(left>=right) return null;
        if(right-left==1) return new TreeNode(nums[left]);

        int mid = left + (right-left)/2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = sortedArrayToBST(nums,left,mid);
        root.right = sortedArrayToBST(nums,mid+1,right);
        return root;
    }
}

538. 把二叉搜索树转换为累加树(抄)

class Solution {
    int sum;
    public TreeNode convertBST(TreeNode root) {
        sum = 0;
        convertBST1(root);
        return root;
    }

    // 按照右中左顺序遍历
    public void convertBST1(TreeNode root){
        if(root==null){
            return;
        }
        convertBST1(root.right);
        sum+=root.val;
        root.val = sum;
        convertBST1(root.left);
    }
}