545.md

545 二叉树的边界

Solution 1

本题主要考察树的遍历, 主要是对叶子节点的判断和路径的选择.

class Solution {
    public List<Integer> boundaryOfBinaryTree(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }

        var result = new ArrayList<Integer>();

        result.add(root.val);

        result.addAll(leftVisit(root.left));

        if (root.left != null || root.right != null) {
            inorderVisit(root, result);
        }

        result.addAll(rightVisit(root.right));
        
        return result;
    }

    private void inorderVisit(TreeNode node, List<Integer> leafs) {
        if (node == null) {
            return;
        }

        inorderVisit(node.left, leafs);

        if (node.left == null && node.right == null) {
            leafs.add(node.val);
        }

        inorderVisit(node.right, leafs);
    }

    private List<Integer> leftVisit(TreeNode node) {
        List<Integer> result = new ArrayList<>();

        while (node != null && (node.left != null || node.right != null)) {
            result.add(node.val);
            if (node.left != null) {
                node = node.left;
            } else {
                node = node.right;
            }
        }

        return result;
    }

    private Stack<Integer> rightVisit(TreeNode node) {
        Stack<Integer> result = new Stack<>();

        while (node != null && (node.left != null || node.right != null)) {
            result.push(node.val);
            if (node.right != null) {
                node = node.right;
            } else {
                node = node.left;
            }
        }

        return result;
    }
}