二叉树DFS

基础知识

二叉树遍历

二叉搜索树BST

二叉树三种深度遍历

LeetCode 94. 二叉树的中序遍历

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        inorder(root, ans);
        return ans;
    }
    public void inorder(TreeNode root, List<Integer> ans) {
        if ( root == null )
            return;
        inorder(root.left, ans);
        ans.add(root.val);
        inorder(root.right, ans);
    }
}

LeetCode 144. 二叉树的前序遍历

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        preorder(root, ans);
        return ans;
    }
    public void preorder(TreeNode root, List<Integer> ans) {
        if ( root == null )
            return;
        ans.add(root.val);
        preorder(root.left, ans);
        preorder(root.right, ans);
    }
}

LeetCode 145. 二叉树的后序遍历

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        postorder(root, ans);
        return ans;
    }
    public void postorder(TreeNode root, List<Integer> ans) {
        if ( root == null )
            return;
        postorder(root.left, ans);
        postorder(root.right, ans);
        ans.add(root.val);
    }
}

从深度遍历序列还原二叉树

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

class Solution {
    // 通过哈希表把中序遍历序列中的值和顺序建立映射关系
    private Map<Integer, Integer> indexMap;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = inorder.length;
        // 构造哈希映射，以中序序列中的元素值 inorder[i] 作为 key，以位置 i 作为 value，存放到哈希表中
        indexMap = new HashMap<Integer, Integer>();
        for (int i=0; i<n; i++) {
            indexMap.put(inorder[i],i);
        }
        return help(preorder, inorder, 0, n-1, 0, n-1);
    }

    public TreeNode help(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {
        if (preorder_left > preorder_right)
            return null;
        // 前序遍历中的第一个节点就是根节点
        int preorder_root = preorder_left;
        // 在中序遍历中定位根节点
        int inorder_root = indexMap.get(preorder[preorder_root]);
        // 构建根节点
        TreeNode root =  new TreeNode(preorder[preorder_root]);
        // 左子树中的节点数目
        int size_left_subtree = inorder_root - inorder_left;
        // 递归地构造左子树，并连接到根节点
        // 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
        root.left = help(preorder, inorder, preorder_left+1, preorder_left+size_left_subtree, inorder_left, inorder_root-1);
        // 递归地构造右子树，并连接到根节点
        // 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
        root.right = help(preorder, inorder, preorder_left+size_left_subtree+1, preorder_right, inorder_root+1, inorder_right);
        return root;
    }

}

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

class Solution {
    // 通过哈希表把中序遍历序列中的值和顺序建立映射关系
    private Map<Integer, Integer> indexMap;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        int n = inorder.length;
        // 构造哈希映射，以中序序列中的元素值 inorder[i] 作为 key，以位置 i 作为 value，存放到哈希表中
        indexMap = new HashMap<Integer, Integer>();
        for (int i=0; i<n; i++) {
            indexMap.put(inorder[i],i);
        }
        return help(inorder, postorder, 0, n-1, 0, n-1);
    }

    public TreeNode help(int[] inorder, int[] postorder, int inorder_left, int inorder_right, int postorder_left, int postorder_right) {
        if (inorder_left > inorder_right)
            return null;
        // 后序遍历中的最后一个节点就是根节点
        int postorder_root = postorder_right;
        // 在中序遍历中定位根节点
        int inorder_root = indexMap.get(postorder[postorder_root]);
        // 构建根节点
        TreeNode root =  new TreeNode(postorder[postorder_root]);
        // 左子树中的节点数目
        int size_left_subtree = inorder_root - inorder_left;
        // 递归地构造左子树，并连接到根节点
        root.left = help(inorder, postorder, inorder_left,inorder_root-1, postorder_left, postorder_left+size_left_subtree-1);
        // 递归地构造右子树，并连接到根节点
        root.right = help(inorder, postorder, inorder_root+1, inorder_right, postorder_left+size_left_subtree, postorder_right-1);
        return root;
    }
}

二叉搜索树BST

LeetCode 700. 二叉搜索树中的搜索

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

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

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

LeetCode 98. 验证二叉搜索树

class Solution {
    public boolean isValidBST(TreeNode root) {
        return check(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public boolean check(TreeNode root, long rangeLeft, long rangeRight) {
        if (root == null)
            return true;
        if (root.val<=rangeLeft || root.val>=rangeRight)
            return false;
        return check(root.left, rangeLeft, root.val) && check(root.right, root.val, rangeRight);
    }
}