力扣热题9-二叉树专题、验证二叉搜索树


按照leetcode刷一遍:leetcode hot

88. 合并两个有序数组

刚开始想复杂了,直接填最大的就行了。

     a *                       b
[1,2,3,0,0,0], m = 3, nums2 = [2,5,6]

待填的槽*必定在a或者a右边,直接写就可以了。

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int a = m-1;
        int b = n-1;
        for(int i=m+n-1;i>=0;i--) {
            if(a>=0&&b>=0&&nums1[a]>=nums2[b]) {
                nums1[i] = nums1[a];
                a--;
            } else {
                if(b>=0) nums1[i] = nums2[b];
                else if(a>=0) return;
                b--;
            }
        }
    }
}

91. 解码方法

一眼动态规划,还ok。

class Solution {
    public int numDecodings(String s) {
        // 1 1 1 0 6
        // a: 前前位
        // b: 前位
        // cur: 当前位置
        // cur = ( if(b cur) ok?a:0 ) + ( if(cur) ok?b:0 )
        if(s.length()==0||s.charAt(0)=='0') {
            return 0;
        }
        int a = 1;
        int b = 1;
        int cur;
        for(int i=1;i<s.length();i++) {
            cur = 0;
            if(s.charAt(i)!='0') {
                cur += b;
            }
            if(s.charAt(i-1)=='1'||
                    s.charAt(i-1)=='2'&&(s.charAt(i)<='6')) {
                cur += a;
            }
            a = b;
            b = cur;
        }
        return b;
    }
}

94. 二叉树的中序遍历

递归

递归没啥难度,应该会问非递归方法。

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

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

非递归

非递归就是把原来用递归栈的东西自己存储起来。

前中后序就是当前结点是在左右结点之前,之间,之后来区分的。中序就是先记录其左节点的值,再记录当前结点值,再记录右结点值,需要用栈记录当前结点就可以了。

/**
 * 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<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if(root==null) {
            return result;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        TreeNode cur = root;
        while(cur!=null) {
            deque.addLast(cur);
            if(cur.left!=null) {
                cur = cur.left;
            } else {
                do {
                    cur = deque.pollLast();
                    if(cur==null) return result;
                    result.add(cur.val);
                    cur = cur.right;
                } while(cur==null);
            }
        }
        return result;
    }
}

98. 验证二叉搜索树

错误答案

class Solution {
    public boolean isValidBST(TreeNode root) {
        if(root==null) return true;
        return (root.left!=null?root.left.val<root.val:true) &&
                (root.right!=null?root.right.val>root.val:true) &&
                isValidBST(root.left) &&
                isValidBST(root.right);
    }
}

忘了考虑这种情况了:

image-20220223211754829

修改了下,还是有问题没考虑到:

image-20220223213028318

这错综复杂,用中序遍历吧,顺序的,应该可行。

中序遍历

随意写的,可以跑:

class Solution {
    public boolean isValidBST(TreeNode root) {
        if(root==null) return true;
        List<Integer> list = new ArrayList<>();
        inorderTrace(root,list);
        for(int i=1;i<list.size();i++) {
            if(list.get(i)<=list.get(i-1)) {
                return false;
            }
        }
        return true;
    }

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

简洁写法(再看看)

/**
 * 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 {
    long pre = Long.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if(root==null) return true;
        if(!isValidBST(root.left)) {
            return false;
        }
        if(root.val<=pre) {
            return false;
        }
        pre = root.val;
        if(!isValidBST(root.right)) {
            return false;
        }
        return true;
    }
}

101. 对称二叉树

image-20220223220101867

遇事不决,递归大法。

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root==null) return true;
        return isSymmetric0(root.left,root.right);
    }

    private boolean isSymmetric0(TreeNode a,TreeNode b) {
        if(a==null&&b==null) return true;
        if(a==null||b==null||a.val!=b.val) return false;
        return isSymmetric0(a.left,b.right)&&isSymmetric0(a.right,b.left);
    }
}

102. 二叉树的层序遍历

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Deque<TreeNode> deque = new LinkedList<>();
        Deque<Integer> layer = new LinkedList<>();
        List<List<Integer>> result = new ArrayList<>();
        if(root==null) return result;
        deque.addLast(root);
        layer.addLast(root.val);
        TreeNode cur = root;
        int curLayerCount = 1;
        int lastLayerCount = 0;
        while(!deque.isEmpty()) {
            if(lastLayerCount==0) {
                lastLayerCount = curLayerCount;
                curLayerCount = 0;
                result.add(new ArrayList(layer));
                layer.clear();
            } else {
                cur = deque.pollFirst();
                lastLayerCount--;
                if(cur.left!=null) {
                    deque.addLast(cur.left);
                    layer.addLast(cur.left.val);
                    curLayerCount++;
                }
                if(cur.right!=null) {
                    deque.addLast(cur.right);
                    layer.addLast(cur.right.val);
                    curLayerCount++;
                }
            }
        }
        return result;
    }
}

104. 二叉树的最大深度

递归

class Solution {
    public int maxDepth(TreeNode root) {
        if(root==null) return 0;
        return Math.max(1+maxDepth(root.left),1+maxDepth(root.right));
    }
}

105. 从前序与中序遍历序列构造二叉树

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeHelper(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
    }

    private TreeNode buildTreeHelper(int[] preorder,int preLeft,int preRight,int[] inorder,int inLeft,int inRight) {
        if(inLeft==inRight) {
            return new TreeNode(inorder[inLeft]);
        } 
        if(inLeft>inRight) {
            return null;
        }
        TreeNode node = new TreeNode(preorder[preLeft]);
        int rootInorderPos = inLeft;
        while(inorder[rootInorderPos]!=preorder[preLeft]) {
            rootInorderPos++;
        }

        int leftPartSize = rootInorderPos-inLeft;
        int rightPartSize = inRight-inLeft+1-1-leftPartSize;
        node.left = buildTreeHelper(preorder,preLeft+1,preLeft+leftPartSize,inorder,inLeft,rootInorderPos-1);
        node.right = buildTreeHelper(preorder,preLeft+leftPartSize+1,preRight,inorder,rootInorderPos+1,inRight);
        return node;
    }
}

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

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return sortedArrayToBSTHelper(nums,0,nums.length-1);
    }

    private TreeNode sortedArrayToBSTHelper(int[] nums,int start,int end) {
        if(start>end) {
            return null;
        }
        if(start==end) {
            return new TreeNode(nums[start]);
        }
        int mid = (start+end)/2;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = sortedArrayToBSTHelper(nums,start,mid-1);
        node.right = sortedArrayToBSTHelper(nums,mid+1,end);
        return node;
    }
}