Java naive solution, just check left boundary leaves and right boundary in order


  • 1
    public List<Integer> boundaryOfBinaryTree(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root==null) return ret;
        Set<TreeNode> visited = new HashSet<>();
        getLeftBound(root,ret,visited);
        getLeaves(root,ret,visited);
        getRightBound(root,ret,visited);
        return ret;
    }
    
    private void getLeftBound(TreeNode root, List<Integer> ret, Set<TreeNode> visited){
        if(root.left==null){
            ret.add(root.val);
            visited.add(root);
            return;
        }
        TreeNode curr = root;
        while(curr!=null){
            ret.add(curr.val);
            visited.add(curr);
            if(curr.left!=null){
                curr = curr.left;
            }
            else if(curr.right!=null){
                curr = curr.right;
            }
            else{
                break;
            }
        }
        return;
    }
    
    private void getLeaves(TreeNode root, List<Integer> ret, Set<TreeNode> visited){
        if(root.left==null&&root.right==null){
            if(!visited.contains(root)){
                ret.add(root.val);
                visited.add(root);
            }
            return;
        }
        if(root.left!=null){
            getLeaves(root.left,ret,visited);
        }
        if(root.right!=null){
            getLeaves(root.right,ret,visited);
        }
    }
    
    private void getRightBound(TreeNode root, List<Integer> ret,Set<TreeNode> visited){
        int pos = ret.size();
        if(root.right==null){
            return;
        }
        TreeNode curr = root.right;
        while(curr!=null){
            if(visited.contains(curr)) break;
            ret.add(pos,curr.val);
            visited.add(curr);
            if(curr.right!=null){
                curr = curr.right;
            }
            else if(curr.left!=null){
                curr = curr.left;
            }
            else{
                break;
            }
        }
        return;
    }

  • 0
    J

    simplify the code.

    public List<Integer> boundaryOfBinaryTree(TreeNode root) {
            List<Integer> ret = new ArrayList<>();
            if(root == null) return ret;
            ret.add(root.val);
            getLeftBound(root.left,ret);
            getLeaves(root.left,ret);
            getLeaves(root.right, ret);
            getRightBound(root.right,ret);
            return ret;
        }
    
        private void getLeftBound(TreeNode root, List<Integer> ret){
            TreeNode curr = root;
            while(curr!=null){
                if(curr.left == null && curr.right == null)
                    break;
                ret.add(curr.val);
                if(curr.left != null){
                    curr = curr.left;
                }
                else{
                    curr = curr.right;
                }
            }
        }
    
        private void getLeaves(TreeNode root, List<Integer> ret){
            if(root == null){
                return;
            }
            if(root.left == null && root.right == null){
                ret.add(root.val);
            }
            if(root.left != null){
                getLeaves(root.left,ret);
            }
            if(root.right != null){
                getLeaves(root.right,ret);
            }
        }
    
        private void getRightBound(TreeNode root, List<Integer> ret){
            int pos = ret.size();
            TreeNode curr = root;
            while(curr!=null){
                if(curr.left == null && curr.right == null)
                    break;
                ret.add(pos, curr.val);
                if(curr.right != null){
                    curr = curr.right;
                }
                else{
                    curr = curr.left;
                }
            }
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.