二叉树

2022-03-02

字数统计: 2.3k字 | 阅读时长: 11分

二叉树的所有路径

https://leetcode.cn/problems/binary-tree-paths/


List<String> result = new ArrayList<>();
List<String> path = new ArrayList<>();
public List<String> binaryTreePaths(TreeNode root) {
    this.backtrack(root);
    return this.result;
}

private void backtrack(TreeNode root) {
    if (root == null) {
        return;
    }
    // 只能当叶子节点的时候保存结果，空的时候保存结果，会保存两遍
    if (root.left == null && root.right == null) {
        this.path.add(root.val + "");
        this.result.add(String.join("->", this.path));
        // 记得在这里也要回溯
        this.path.remove(this.path.size() - 1);
        return;
    }

    for (int i = 0; i < 2; i++) {
        this.path.add(root.val + "");
        if (i == 0) {
            backtrack(root.left);
        } else {
            backtrack(root.right);
        }
        this.path.remove(this.path.size() - 1);
    }
}

平衡二叉树

https://leetcode.cn/problems/balanced-binary-tree/

public boolean isBalanced(TreeNode root) {
    if (root == null) {
        return true;
    }
    return Math.abs(this.getHeight(root.left) - this.getHeight(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}

private int getHeight(TreeNode root) {
    if (root == null) {
        return 0;
    }
    return Math.max(getHeight(root.left), getHeight(root.right)) + 1;
}

二叉树对称

https://leetcode.cn/problems/symmetric-tree/

对称条件，对应位置的节点值相等，对应位置的左节点与右节点，右节点与左节点是相同的。

public boolean isSymmetric(TreeNode root) {
   return this.isSame(root.left, root.right);
}

private boolean isSame(TreeNode root1, TreeNode root2) {
    if (root1 == null || root2 == null) {
        return root1 == root2;
    }
    return root1.val == root2.val && isSame(root1.left, root2.right) && isSame(root1.right, root2.left);
}

二叉树相同

https://leetcode.cn/problems/same-tree/

相同条件：相同位置值相同，左右孩子也相同

public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null || q == null) {
        return p == q;
    }
    return p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

相同子树

https://leetcode.cn/problems/subtree-of-another-tree/

遍历节点，进行比较

public boolean isSubtree(TreeNode root, TreeNode subRoot) {
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode current = queue.remove();
        if (this.isSame(current, subRoot)) {
            return true;
        }
        if (current.left != null) {
            queue.add(current.left);
        }
        if (current.right != null) {
            queue.add(current.right);
        }
    }
    return false;
}

private boolean isSame(TreeNode root1, TreeNode root2) {
    if (root1 == null || root2 == null) {
        return root1 == root2;
    }
    return root1.val == root2.val && isSame(root1.left, root2.left) && isSame(root1.right, root2.right);
}

左叶子节点和

使用递归前序遍历，借助遍历isLeft标记是左节点，如果同时是叶子节点还是左节点的话，就累加该值

private boolean isLeft = false;
private int sum = 0;
public int sumOfLeftLeaves(TreeNode root) {
    this.helper(root);
    return this.sum;
}

public void helper(TreeNode root) {
    if (root == null) {
        return;
    }
    if (root.left == null && root.right == null && this.isLeft) {
        this.sum += root.val;
    }
    this.isLeft = true;
    helper(root.left);
    this.isLeft = false;
    helper(root.right);
}

代码随想录解法

public int sumOfLeftLeaves(TreeNode root) {
    if (root == null) return 0;
    int current = 0;
    // 左节点不为空，并且是叶子节点，加上该值
    if (root.left != null && root.left.left == null && root.left.right == null) {
        current = root.left.val;
    }
    return current + sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
}

左下角的值

https://leetcode.cn/problems/find-bottom-left-tree-value/

层序遍历

public int findBottomLeftValue(TreeNode root) {
    Deque<TreeNode> queue = new ArrayDeque<TreeNode>();
    queue.add(root);
    int result = root.val;
    while (!queue.isEmpty()) {
        int size = queue.size();
        int i = 0;
        while (i < size) {
            TreeNode current = queue.remove();
            if (i == 0) {
                result = current.val;
            }
            if (current.left != null) {
                queue.add(current.left);
            }
            if (current.right != null) {
                queue.add(current.right);
            }
            i++;
        }
    }
    return result;
}

回溯搜索
在当前层判断了下一层的元素，应该不是最简单的逻辑，还可以再精简。

private int result = 0;
private int maxHeight = 0;
private int currentHeight = 0;
public int findBottomLeftValue(TreeNode root) {
    this.backtrack(root);
    return this.result;
}

private void backtrack(TreeNode root) {
    if (root.left == null && root.right == null) {
        if (this.currentHeight + 1 > this.maxHeight) {
            this.maxHeight = this.currentHeight + 1;
            this.result = root.val;
        }
        return;
    }
    
    if (root.left != null) {
        this.currentHeight++;
        backtrack(root.left);
        this.currentHeight--;
    }
    
    if (root.right != null) {
        this.currentHeight++;
        backtrack(root.right);
        this.currentHeight--;
    }
}

优化，当前层只处理当前层的值，不提前判断下一层的值

    private int result = 0;
    private int maxHeight = 0;
    public int findBottomLeftValue(TreeNode root) {
        this.backtrack(root, 0);
        return this.result;
    }

    private void backtrack(TreeNode root, int currentHeight) {
        if (root == null) {
            return;
        }
        // 叶子节点结束递归
        if (root.left == null && root.right == null) {
            // 隐藏着回溯，如果是当前层第一个节点，就保存结果
            if (currentHeight + 1 > this.maxHeight) {
                this.maxHeight = currentHeight + 1;
                this.result = root.val;
            }
            return;
        }
        
        // 递归函数的第一个参数：下一层的节点
        // 递归函数的第二个参数：加上本层的高度
        // 总结：如果需要在参数中隐藏回溯，隐藏回溯的参数处理的是本层的值，其他参数都是下一层的初始化参数
        backtrack(root.left, currentHeight + 1);
        backtrack(root.right, currentHeight + 1);
    }

合并二叉树

https://leetcode.cn/problems/merge-two-binary-trees/

// 函数的意义就是合并两棵树，返回合并后的根节点
public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
    if (root1 == null) {
        return root2;
    }
    if (root2 == null) {
        return root1;
    }
    
    root1.val += root2.val;
    root1.left = mergeTrees(root1.left, root2.left);
    root1.right = mergeTrees(root1.right, root2.right);
    return root1;
}

二叉搜索树中的搜索

https://leetcode.cn/problems/search-in-a-binary-search-tree/

// 递归函数的意义，找到节点值等于val的节点并返回
public TreeNode searchBST(TreeNode root, int val) {
    // 短路或，防止root NPE
    if (root == null || root.val == val) {
        return root;
    }
    // 值在左子树
    if (val < root.val) {
        return searchBST(root.left, val);
    }
    // 值在右子树
    if (val > root.val) {
        return searchBST(root.right, val);
    }
    // 不可能出现这种情况，防止报错
    return null;
}

路径总和

如果只搜索二叉树中满足条件的一条路径，找到后可以立即返回，需要返回值。

如果搜索整棵树，但需要处理递归的结果，需要返回值。

如果搜索整棵树，不需要处理递归结果，不需要返回值。

一条路径
https://leetcode.cn/problems/path-sum/

public boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) {
        return false;
    }
    if (root.left == null && root.right == null) {
        if (targetSum - root.val == 0) {
            return true;
        } else {
            return false;
        }
    }
    // 当前层要处理当前值，不能在当前层处理下一层得值
    // 左子树找到了叶子节点是目标和，立即返回
    if (hasPathSum(root.left, targetSum - root.val)) {
        return true;
    }
    // 右子树找到了叶子节点是目标和，立即返回
    if (hasPathSum(root.right, targetSum - root.val)) {
        return true;
    }
    // 左右都不满足，返回false
    return false;
}

整棵树
https://leetcode.cn/problems/path-sum-ii/

private List<Integer> path = new ArrayList<>();
private List<List<Integer>> result = new ArrayList<>(); 
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
    backtrack(root, targetSum);
    return result;
}

private void backtrack(TreeNode root, int targetSum) {
    // 空结点结束递归
    if (root == null) {
        return;
    }
    // 叶子节点结束递归
    if (root.left == null && root.right == null) {
        // 满足目标和
        if (targetSum - root.val == 0) {
            path.add(root.val);
            // 要新建，不然只是引用
            result.add(new ArrayList<>(path));
            path.remove(path.size() - 1);
        }
        return;
    }
    // 当前层的值都相同，递归到下一层时，都要带着当前层的值，只需要在返回至上一层时，删除当前层值即可
    // 只用选择当前节点以及撤销操作，即回溯一次
    path.add(root.val);
    backtrack(root.left, targetSum - root.val);
    backtrack(root.right, targetSum - root.val);
    path.remove(path.size() - 1);
}

中序遍历与后序遍历构造二叉树

https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/

先切割中序遍历的数组，根据切割后的中序遍历数组的长度，切割后续遍历数组

public TreeNode buildTree(int[] inorder, int[] postorder) {
    if (inorder.length == 0) {
        return null;
    }
    int value = postorder[postorder.length - 1];
    int index = this.getIndex(value,inorder);
    // 索引的左边
    int[] leftInorder = Arrays.copyOfRange(inorder, 0, index);
    // 索引的右边
    int[] rightInorder = Arrays.copyOfRange(inorder, index + 1, inorder.length);
    // [0, leftInorder长度)
    int[] leftPostorder = Arrays.copyOfRange(postorder, 0, leftInorder.length);
    // [leftInorder长度, postOrder长度 - 1)
    int[] rightPostorder = Arrays.copyOfRange(postorder, leftInorder.length, postorder.length - 1);
    
    TreeNode node = new TreeNode(value);
    node.left = buildTree(leftInorder, leftPostorder);
    node.right = buildTree(rightInorder, rightPostorder);
    return node;
}

private int getIndex(int value, int[] inorder) {
    for (int i = 0; i < inorder.length; i++) {
        if (value == inorder[i]) {
            return i;
        }
    }
    return -1;
}

前序遍历与中序遍历构造二叉树

https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

public TreeNode buildTree(int[] preorder, int[] inorder) {
    if (preorder.length == 0) {
        return null;
    }
    int value = preorder[0];
    int index = this.getIndex(value, inorder);
    int[] leftInorder = Arrays.copyOfRange(inorder, 0, index);
    int[] rightInorder = Arrays.copyOfRange(inorder, index + 1, inorder.length);
    int[] leftPreorder = Arrays.copyOfRange(preorder, 1, leftInorder.length + 1);
    int[] rightPreorder = Arrays.copyOfRange(preorder, leftInorder.length + 1, preorder.length);
    
    TreeNode node = new TreeNode(value);
    node.left = buildTree(leftPreorder, leftInorder);
    node.right = buildTree(rightPreorder, rightInorder);
    return node;
}

private int getIndex(int value, int[] inorder) {
    for (int i = 0; i < inorder.length; i++) {
        if (value == inorder[i]) {
            return i;
        }
    }
    return -1;
}

最大二叉树

https://leetcode.cn/problems/maximum-binary-tree/

public TreeNode constructMaximumBinaryTree(int[] nums) {
    if (nums.length == 0) {
        return null;
    }
    int maxIndex = this.getIndexOfMax(nums);
    int[] leftNums = Arrays.copyOfRange(nums, 0, maxIndex);
    int[] rightNums = Arrays.copyOfRange(nums, maxIndex + 1, nums.length);
    TreeNode node = new TreeNode(nums[maxIndex]);
    node.left = constructMaximumBinaryTree(leftNums);
    node.right = constructMaximumBinaryTree(rightNums);
    return node;
}

private int getIndexOfMax(int[] nums) {
    int maxIndex = 0;
    for (int i = 1; i < nums.length; i++) {
        if (nums[i] > nums[maxIndex]) {
            maxIndex = i;
        }
    }
    return maxIndex;
}