算法第十七天|二叉树

617. 合并二叉树

  public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if (root1 == null) {
            return root2;
        }
        if (root2 == null) {
            return root1;
        }
        TreeNode treeNode = new TreeNode(root1.val + root2.val);

        treeNode.left = mergeTrees(root1.left, root2.left);
        treeNode.right = mergeTrees(root1.right, root2.right);
        return treeNode;
    }

700. 二叉搜索树中的搜索

  public TreeNode searchBST(TreeNode root, int val) {
        // 二叉搜索树，根节点比左子树所有节点的值都大，比右子树所有根节点的值都小
        if (root == null) {
            return null;
        }

        if (root.val > val) {
            return searchBST(root.left, val);
        } else if (root.val < val){
            return searchBST(root.right, val);
        } else  {
            return root;
        }
    }

98. 验证二叉搜索树

 private List<Integer> list = new ArrayList<>();

    public boolean isValidBST(TreeNode root) {
        // 二叉搜索树，中序遍历的结果是一个有序序列
        getPreList(root);
        int preValue = list.get(0);
        for (int i = 1; i < list.size(); i++) {
            if (list.get(i) <= preValue) {
                return false;
            } else {
                preValue = list.get(i);
            }
        }
        return true;
    }

    private void getPreList(TreeNode root) {
        if (root == null) {
            return;
        }
        getPreList(root.left);
        list.add(root.val);
        getPreList(root.right);
    }

注意一点：二叉搜索树，中序遍历的结果是一个有序序列。只要知道这一点，问题就可以轻松解答了